1008. 贪婪大陆
★★ 输入文件：greedisland.in 输出文件：greedisland.out 简单对比
时间限制：1 s 内存限制：128 MB
随手打了一个区间最大值线段树，然而才发现......
维护两个bit c1区间开始和c2区间结束
对于[l,r]加操作，add(c1,l,1);add(c2,r,1);
然后查询就是r之间开始的区间-l之前结束的区间（不包括l这个点）
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=1e5+5; inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } int n,M,Q,l,r; int c1[N],c2[N]; inline int lowbit(int x){return x&-x;} void add(int c[],int x,int d){for(int i=x;i<=n;i+=lowbit(i)) c[i]+=d; } int sum(int c[],int x){int res=0;for(int i=x;i>0;i-=lowbit(i)) res+=c[i];return res; } int main(int argc, const char * argv[]){freopen("greedisland.in","r",stdin);freopen("greedisland.out","w",stdout);n=read();M=read();while(M--){Q=read();l=read();r=read();if(Q==1){add(c1,l,1);add(c2,r,1);}else printf("%d\n",sum(c1,r)-sum(c2,l-1));}return 0; }