题解 | #简单题#

简单题

思路

转为括号序列，左括号：区间左端点，右括号：区间右端点
t = 1 时，L 处的左括号数目加 1，R 处的右括号数目加 1
t = 2 时，令 [1,x] 区间的左括号数目 减去 [1,x-1] 区间的右括号数目 = k
k 就是 位置 x 上的元素（初始为0） 的变化次数，k 为偶数 答案为 0，否则为 1

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5+10;

int tr[N],trr[N];
int n,m;

int lowbit(int x){
    return  x & -x;
}

void add(int t[],int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)) t[i]+=v;
}

int sum(int t[],int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))  res+=t[i];
    return res;
}

int query(int x){
    return sum(tr,x)-sum(trr,x-1);
}

int main(){
    cin>>n>>m;
    int t,l,r;
    while(m--){
        cin>>t;
        if(t==1) cin>>l>>r,add(tr,l,1),add(trr,r,1);
        else{
            cin>>l;
            if(query(l)&1) puts("1");
            else puts("0");
        } 
    }

    return 0;
}