原题
//codevs1299 切水果 #include<iostream> #include<cstdio> #include<cstring> #define lson l,m,pos<<1 #define rson m+1,r,pos<<1|1 using namespace std; int n,m; int sum[20050000]; int read() { int ret=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')ret=ret*10+c-'0',c=getchar(); return ret; } void pushup(int pos){sum[pos]=sum[pos<<1]+sum[pos<<1|1];} void build(int l,int r,int pos) { if (l==r) {sum[pos]=1;return;} int m=(l+r)>>1; build(lson);build(rson); pushup(pos); } void update(int LL,int RR,int l,int r,int pos) { if (!sum[pos]) return; if (LL<=l&&r<=RR) {sum[pos]=0;return;} int m=(l+r)>>1; if (LL<=m) update(LL,RR,lson); if (RR>m) update(LL,RR,rson); pushup(pos); } int main() { n=read();m=read(); build(1,n,1); while(m--) { int a=read(),b=read(); update(a,b,1,n,1); printf("%d\n",sum[1]); } return 0; }
