首页 > 代码库 > [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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。