首页 > 代码库 > [TYVJ1473]校门外的树3

[TYVJ1473]校门外的树3

思路:

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

 1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 inline int getint() { 5     char ch; 6     while(!isdigit(ch=getchar())); 7     int x=ch^0; 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^0); 9     return x;10 }11 const int N=50001;12 int n;13 class FenwickTree {14     private:15         int val[N];16         int lowbit(const int x) {17             return x&-x;18         }19     public:20         FenwickTree() {21             memset(val,0,sizeof val);22         }23         void modify(int p) {24             while(p<=n) {25                 val[p]++;26                 p+=lowbit(p);27             }28         }29         int query(int p) {30             int ans=0;31             while(p) {32                 ans+=val[p];33                 p-=lowbit(p);34             }35             return ans;36         }37 };38 FenwickTree t[2];39 int main() {40     n=getint();41     for(int m=getint(),cnt=0;m;m--) {42         int op=getint(),l=getint(),r=getint();43         if(op==1) {44             t[0].modify(n+1-l);45             t[1].modify(r);46             cnt++;47         }48         if(op==2) {49             printf("%d\n",cnt-t[0].query(n-r)-t[1].query(l-1));50         }51     }52     return 0;53 }

 

[TYVJ1473]校门外的树3