思路：
线段树区间修改。标记记录当前区间是否被切。
1 #include<cstdio> 2 #include<cctype> 3 #include<cstring> 4 #include<algorithm> 5 inline int getint() { 6 char ch; 7 while(!isdigit(ch=getchar())); 8 int x=ch^'0'; 9 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 10 return x; 11 } 12 class SegmentTree { 13 #define _left <<1 14 #define _right <<1|1 15 private: 16 static const int N=500001; 17 int val[N<<2]; 18 bool tag[N<<2]; 19 void push_down(const int p,const int b,const int e) { 20 if(!tag[p]) return; 21 tag[p _left]=tag[p _right]=true; 22 tag[p]=false; 23 int mid=(b+e)>>1; 24 val[p _left]=mid-b+1; 25 val[p _right]=e-mid; 26 } 27 void push_up(const int p) { 28 val[p]=val[p _left]+val[p _right]; 29 } 30 public: 31 SegmentTree() { 32 memset(val,0,sizeof val); 33 memset(tag,0,sizeof tag); 34 } 35 void modify(const int p,const int b,const int e,const int l,const int r) { 36 if((l<=b)&&(e<=r)) { 37 val[p]=e-b+1; 38 tag[p]=true; 39 return; 40 } 41 push_down(p,b,e); 42 int mid=(b+e)>>1; 43 if(l<=mid) modify(p _left,b,mid,l,r); 44 if(r>mid) modify(p _right,mid+1,e,l,r); 45 push_up(p); 46 } 47 int query() { 48 return val[1]; 49 } 50 }; 51 SegmentTree t; 52 int main() { 53 int n=getint(); 54 for(int m=getint();m;m--) { 55 int l=getint(),r=getint(); 56 t.modify(1,1,n,l,r); 57 printf("%d ",n-t.query()); 58 } 59 return 0; 60 }