题解

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc (p<<1)
#define rc ((p<<1)|1)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N = 400005, inf = 0x3f3f3f3f;
int n, q, a[N], b[N];
struct Node1{
    int l, r, tag, p001, p110, p101, p010;
};
struct Segtree1{
    Node1 tr[4 * N];
    void pushup(int p)
    {
        tr[p].p110 = min(tr[lc].p110, tr[rc].p110);
        tr[p].p001 = min(tr[lc].p001, tr[rc].p001);
        tr[p].p101 = min(tr[lc].p101, tr[rc].p101);
        tr[p].p010 = min(tr[lc].p010, tr[rc].p010);
    }
    void pushdown(int p)
    {
        if(tr[p].tag)
        {
            tr[lc].tag ^= 1;
            tr[rc].tag ^= 1;
            swap(tr[lc].p001, tr[lc].p110);
            swap(tr[lc].p101, tr[lc].p010);
            swap(tr[rc].p001, tr[rc].p110);
            swap(tr[rc].p101, tr[rc].p010);
        }
        tr[p].tag = 0;
    }
    void build(int p, int ln, int rn)
    {
        tr[p]={ln, rn, 0, b[ln]==1 ? ln : inf, b[ln]==2 ? ln : inf, b[ln]==3 ? ln : inf, b[ln]==4 ? ln : inf};
        if(ln == rn)return;
        int mid = (ln + rn) >> 1;
        build(lc, ln, mid);
        build(rc, mid+1, rn);
        pushup(p);
    }
    void update(int p, int ln, int rn)
    {
        if(ln <= tr[p].l && tr[p].r <= rn)
        {
            tr[p].tag ^= 1;
            swap(tr[p].p001, tr[p].p110);       
            swap(tr[p].p010, tr[p].p101);   
            return;     
        }
        pushdown(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(ln <= mid)update(lc, ln, rn);
        if(rn >= mid + 1)update(rc, ln, rn);
        pushup(p);
    }
    void modify(int p, int pos, int tp)
    {
        if(tr[p].l == pos && tr[p].r == pos)
        {
            tr[p].p001 = tr[p].p110 = tr[p].p010 = tr[p].p101 = inf;
            if(tp == 0)tr[p].p001 = pos;
            else if(tp == 1)tr[p].p110 = pos;
            else if(tp == 2)tr[p].p010 = pos;
            else if(tp == 3)tr[p].p101 = pos;
            return;
        }
        pushdown(p);
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(pos <= mid)modify(lc, pos, tp);
        else modify(rc, pos, tp);
        pushup(p);
    }
}tr1;
struct BIT{
    bitset<N> tr;
    int lowbit(int x){return (x&(-x));}
    void init()
    {
        for(int i=0;i<=n+1;i++)tr[i]=0;
    }
    int query(int x)
    {
        int res=0;
        while(x)
        {
            res^=tr[x];
            x-=lowbit(x);
        }
        return res;
    }
    void update(int x)
    {
        while(x<=n)
        {
            tr[x]=(tr[x]^1);
            x+=lowbit(x);
        }
    }
}tr2;
ll ans;
inline int chktyp(int x)
{
    int aa = tr2.query(x), bb = tr2.query(x+1), cc = tr2.query(x+2);
    if(aa == 0 && bb == 0 && cc == 1)return 0;
    if(aa == 1 && bb == 1 && cc == 0)return 1;
    if(aa == 0 && bb == 1 && cc == 0)return 2;
    if(aa == 1 && bb == 0 && cc == 1)return 3;
    return 4;
}
int getans()
{
    int res = tr1.tr[1].p110;
    if(res == inf)
    {
        if(tr1.tr[1].p101==inf)return 0;
        return 1;
    }
    return n - res - 1;
}
void solve()
{
    cin >> n >> q;
    tr2.init();
    for(int i = 1; i <= n; i++)
    {
        char c;
        cin >> c;
        a[i] = c - '0';
        b[i] = 0;
        if(a[i])
        {
            tr2.update(i);
            tr2.update(i+1);
        }
    }
    for(int i = 1; i <= n-2; i++)
    {
        if(a[i] == 0 && a[i+1] == 0 && a[i+2] == 1)b[i] = 1;
        if(a[i] == 1 && a[i+1] == 1 && a[i+2] == 0)b[i] = 2;
        if(a[i] == 1 && a[i+1] == 0 && a[i+2] == 1)b[i] = 3;
        if(a[i] == 0 && a[i+1] == 1 && a[i+2] == 0)b[i] = 4;
    }
    tr1.build(1, 1, n-2);
    ans = getans();
    for(int i = 1; i <= q; i++)
    {
        int l, r;
        cin >> l >> r;
        tr2.update(l);
        tr2.update(r + 1);
        if(l == r)
        {
            if(l-2 >= 1 && l-2 <= n-2)tr1.modify(1, l-2, chktyp(l-2));
            if(l-1 >= 1 && l-1 <= n-2)tr1.modify(1, l-1, chktyp(l-1));
            if(l <= n-2)tr1.modify(1, l, chktyp(l));
        }
        else
        {
            if(l <= n-2 && l <= min(r-2,n-2))tr1.update(1, l, min(r-2,n-2));
            if(l-2 >= 1 && l-2 <= n-2)tr1.modify(1, l-2, chktyp(l-2));
            if(l-1 >= 1 && l-1 <= n-2)tr1.modify(1, l-1, chktyp(l-1));
            if(r-1 >= 1 && r-1 <= n-2)tr1.modify(1, r-1, chktyp(r-1));
            if(r <= n-2)tr1.modify(1, r, chktyp(r));            
        }
        ans ^= (1ll * (i+1) * getans());
    }
    cout << ans << '\n';
}
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);




    int cid, t;
    cin >> cid >> t;
    while(t--)solve();
   return 0;
}
@ZHR100102