对于 50% 的数据，1≤n≤10^3,1≤m≤10^4
对于 100% 的数据，1≤n≤10^5,1≤m≤5×10^5,保证 L≤R
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const long long maxn=100010;
int n, k;
inline void qread(int &x){
x = 0;
int ch = getchar();
while(ch < ‘0‘ || ch > ‘9‘) ch =getchar();
while(ch >=‘0‘ && ch <= ‘9‘) x = 10 * x + ch - 48, ch = getchar();
}
struct BItree{
int data[maxn];
BItree(){
memset(data, 0, sizeof(data));
}
void add(int x, int v){
for(; x <= n; x += (x&-x))
data[x] += v;
}
int sum(int x){
int ans = 0;
for(; x; x -= (x&-x))
ans += data[x];
return ans;
}
};
int main(void)
{
BItree change;
qread(n);
qread(k);
while(k--){
int op;
qread(op);
if(op == 1){
int y, z;
qread(y), qread(z);
change.add(y, 1);
change.add(z + 1, 1);
}
else{
int y;
qread(y);
printf("%d\n", change.sum(y)&1);
}
}
}
思路：
以树状数组统计自1-i数列变化的次数，若变化数为奇，值为1， 否则为0
