题解 | #校门外的树#

校门外的树

思路

转为括号序列，左括号：区间左端点，右括号：区间右端点
k = 1 时，l 处的左括号数目加 1，r 处的右括号数目加 1
k = 2 时，[1,r] 区间的左括号数目 减去 [1,l-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 l,int r){
    return sum(tr,r)-sum(trr,l-1);
}

int main(){
    cin>>n>>m;
    while(m--){
        int k,l,r;
        cin>>k>>l>>r;
        if(l>r) swap(l,r);
        if(k==1) add(tr,l,1),add(trr,r,1);
        else cout<<query(l,r)<<endl;
    }

    return 0;
}