http://codevs.cn/problem/1191/
这个数据范围是要nlogn的做法嘛。 线段树：一开始把数组全设为1，建一下树，然后修改的时候把白球全修改成0，每次用线段树求和就好了。 不过我确实调了一个上午啊。感谢sxb大神帮我找错
#include<iostream> #include<cstdio> #define M 200000 #define LL long long using namespace std; int n,m; int a[M+5]; struct H{ int x; int l,r; }st[5*M]; void build(int o,int l,int r) { st[o].l=l,st[o].r=r; if(l==r) { st[o].x=a[l]; return; } int mid=(l+r)/2; build((o<<1),l,mid); build((o<<1)|1,mid+1,r); st[o].x=st[(o<<1)].x+st[o<<1|1].x; } void pushdown(int o) { st[o<<1].x=0; st[o<<1|1].x=0; } void ex(int o,int ql,int qr) { int l=st[o].l,r=st[o].r; int mid=(l+r)/2; if(l==ql&&r==qr) { st[o].x=0; return; } if(!st[o].x) pushdown(o); if(qr<=mid) ex(o<<1,ql,qr); else if(ql>mid) ex(o<<1|1,ql,qr); else ex(o<<1,ql,mid),ex(o<<1|1,mid+1,qr); st[o].x=st[o<<1].x+st[o<<1|1].x; } int query(int o,int ql,int qr) { int l=st[o].l,r=st[o].r; int mid=(l+r)/2; if(ql==l&&qr==r) return st[o].x; if(!st[o].x) pushdown(o); int sum=0; if(ql<=mid) sum+=query(o<<1,ql,mid); if(qr>mid) sum+=query(o<<1|1,mid+1,qr); return sum; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) a[i]=1; build(1,1,n); while(m--) { int L,R,ans; scanf("%d %d",&L,&R); ex(1,L,R); ans=query(1,1,n); printf("%d\n",ans); } return 0; }