[TYVJ1473]校门外的树3

思路：

维护两个树状数组，一个记录种树区间左端点，一个记录右端点。
每次询问查询“看不见的树区间”，即右端点小于查询区间左端点和左端点小于查询区间右端点。

#include<cstdio>
#include<cctype>
#include<cstring>
inline int getint() {
    char ch;
    while(!isdigit(ch=getchar()));
    int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=50001;
int n;
class FenwickTree {
    private:
        int val[N];
        int lowbit(const int x) {
            return x&-x;
        }
    public:
        FenwickTree() {
            memset(val,0,sizeof val);
        }
        void modify(int p) {
            while(p<=n) {
                val[p]++;
                p+=lowbit(p);
            }
        }
        int query(int p) {
            int ans=0;
            while(p) {
                ans+=val[p];
                p-=lowbit(p);
            }
            return ans;
        }
};
FenwickTree t[2];
int main() {
    n=getint();
    for(int m=getint(),cnt=0;m;m--) {
        int op=getint(),l=getint(),r=getint();
        if(op==1) {
            t[0].modify(n+1-l);
            t[1].modify(r);
            cnt++;
        }
        if(op==2) {
            printf("%d
",cnt-t[0].query(n-r)-t[1].query(l-1));
        }
    }
    return 0;
}