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 <<114     #define _right <<1|115     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",n-t.query());58     }59     return 0;60 }