维护一个lazy（表示这段区间被反转了多少次）

时间复杂度 $O(mlogn)$

C++ 代码

#include <iostream>

using namespace std;
const int N = 1e5 + 10;
int tree[N << 2];
int lazy[N << 2];
void pushdown(int l,int r,int u)
{
    int mid = (l + r) >> 1;
    if(lazy[u] % 2){
        tree[u << 1] ^= 1;
        tree[u << 1 | 1] ^= 1;
        lazy[u << 1] ++;
        lazy[u << 1 | 1] ++;
        lazy[u] = 0;
    }else{
        lazy[u] = 0;
    }
}
void update(int l,int r,int a,int b,int u)
{
    if(l <= a && r >= b)
    {
        tree[u] ^= 1;
        lazy[u] ++;
        return ;
    }
    pushdown(a,b,u);
    int mid = (a + b) >> 1;
    if(l <= mid)update(l,r,a,mid,u << 1);
    if(r > mid) update(l,r,mid+1,b,u << 1 | 1);
}
int query(int l,int r,int a,int b,int u)
{
    // 
    if(l <= a && r >= b)
    {
        return tree[u];
    }
    pushdown(a,b,u);
    int mid = (a + b) >> 1;
    if(l <= mid)return query(l,r,a,mid,u << 1);
    else return query(l,r,mid+1,b,u << 1 | 1);
}
int main()
{
    int n,m;
    cin >> n >> m;
    int l,r,x,t;
    for(int i = 1;i <= m;i ++)
    {
        scanf("%d",&t);
        if(t == 1)
        {
            scanf("%d%d",&l,&r);
            update(l,r,1,n,1);
        }else{
            scanf("%d",&x);
            printf("%d\n",query(x,x,1,n,1));
        }
    }
}