Description

Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委

员 会为选民准备了一个张贴海报的electoral墙。张贴规则如下：

1．electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；

2．所有张贴的海报的高度必须与electoral墙的高度一致的；

3．每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；

4．后贴的海报可以覆盖前面已贴的海报或部分海报。

现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。

Input

第一行： N M 分别表示electoral墙的长度和海报个数

接下来M行: Ai Bi 表示每张海报张贴的位置

Output

输出贴完所有海报后，在electoral墙上还可以看见的海报数。

1 0<= N <= 10000000 1<=M<=1000 1<= Ai <= Bi <=10000000

所有的数据都是整数。数据之间有一个空格

Sample Input

100 5

1 4

2 6

8 10

3 4

7 10

Sample Output

4

Solution

裸的线段树区间覆盖的题目，覆盖一下最后统计一波就好了

Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define N (1000000+100) 6 using namespace std; 7  8 int Segt[N<<2]; 9 int n,m,x[N],y[N],id[N],cnt,num,ans;10 bool vis[N];11 12 void Pushdown(int now)13 {14     if (Segt[now])15     {16         Segt[now<<1]=Segt[now];17         Segt[now<<1|1]=Segt[now];18         Segt[now]=0;19     }20 }21 22 void Update(int now,int l,int r,int l1,int r1,int k)23 {24     if (l>r1 || r
          
           >1;28     Update(now<<1,l,mid,l1,r1,k);29     Update(now<<1|1,mid+1,r,l1,r1,k);30 }31 32 int Query(int now,int l,int r,int x)33 {34     if (l==r) return Segt[now];35     Pushdown(now);36     int mid=(l+r)>>1;37     if (x<=mid) return Query(now<<1,l,mid,x);38     else return Query(now<<1|1,mid+1,r,x);39 }40 41 int getid(int x)42 {43     int l=1,r=num;44     while (l<=r)45     {46         int mid=(l+r)>>1;47         if (id[mid]==x) return mid;48         if (x