树状数组帅炸了。。。。又被一道水题轻虐，又被学长指出了一个错误。。。。我太菜了QAQ

开两个树状数组，一个记录左端点，一个记录右端点；

共有cnt(总数) – (<l的右端点数目) – (>r的右端点数目) 种地雷

#include<cstdio>
#include<iostream>
#define R register int
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==\'-\'?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int n,c[2][100010],m,cnt;
inline int max(int a,int b) {return a>b?a:b;}
inline int lbt(int x) {return x&(-x);}
inline void add(int k,int pos) {for(;pos<=n;pos+=lbt(pos)) ++c[k][pos];}
inline int query(int k,int pos) { R ret=0;
    for(;pos;pos-=lbt(pos)) ret+=c[k][pos]; return ret;    
}
signed main() {
    n=g(),m=g();
    for(R i=1;i<=m;++i) {
        R k=g(),l=g(),r=g();
        if(k&1) add(0,l),add(1,r),++cnt;
        else printf("%d\n",cnt-query(1,l-1)-query(0,n)+query(0,r));
    }
}

2019.04.07

 

版权声明：本文为Jackpei原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Jackpei/p/10665163.html