[acwing] 1268. Simple questions

Title address ：

https://www.acwing.com/problem/content/1270/

There is one $n$ Array of elements , Each element is initially $0$. Yes $m$ Orders , Or reverse one of the consecutive numbers ——$0$ change $1$,$1$ change $0$（ operation $1$）, Or ask for the value of an element （ operation $2$）. For example, when $n=20$ when ,$10$ The instructions are as follows ：

Input format ：
The first line contains two integers $n,m$, Represents the length of the array and the number of instructions ;
following $m$ That's ok , The first number of each line $t$ Indicates the type of operation ：
if $t=1$, Then there are two numbers $L,R$, Indicates the interval $[L,R]$ Every number of is reversed ;
if $t=2$, Then there is only one number $i$, Subscript indicating inquiry （ Array index from $1$ Start ）.

Output format ：
Each operation $2$ Output one line （ Not $0$ namely $1$）, Indicates each operation $2$ Answer .

Data range ：
$1\le n\le 10^5$
$1\le m\le 5\times 10^5$
Guarantee $L\le R$

Because flipping is equivalent to non carry addition , Thus equivalent to XOR , So let's consider a differential array , And maintain it with a tree array . The difference of this difference array is XOR （ namely $A$ The differential array of $c[i]=A[i]\wedge A[i-1]$）. So flip $A[l:r]$ Equivalent to $c[l]=c[l]\wedge 1,c[r+1]=c[r+1]\wedge 1$, Asking is equivalent to finding prefix XOR and . The code is as follows ：

#include <iostream>
#define lowbit(x) (x & -x)
using namespace std;

const int N = 1e5 + 10;
int n, m;
int tr[N];

void add(int k, int x) {
    
  for (; k <= n; k += lowbit(k)) tr[k] ^= x;
}

int sum(int k) {
    
  int res = 0;
  for (; k; k -= lowbit(k)) res ^= tr[k];
  return res;
}

int main() {
    
  scanf("%d%d", &n, &m);
  while (m--) {
    
    int t, l, r, k;
    scanf("%d", &t);
    if (t == 1) {
    
      scanf("%d%d", &l, &r);
      add(l, 1);
      add(r + 1, 1);
    } else {
    
      scanf("%d", &k);
      printf("%d\n", sum(k));
    }
  }
}

Time complexity of each operation $O(\log n)$, Space $O(n)$.