题目描述
Bytetown城市要进行市长竞选，所有的选民可以畅所欲言地对竞选市长的候选人发表言论。为了统一管理，城市委员会为选民准备了一个张贴海报的electoral墙。
张贴规则如下：
electoral墙是一个长度为N个单位的长方形，每个单位记为一个格子；
所有张贴的海报的高度必须与electoral墙的高度一致的；
每张海报以“A B”表示，即从第A个格子到第B个格子张贴海报；
- 后贴的海报可以覆盖前面已贴的海报或部分海报。
现在请你判断，张贴完所有海报后，在electoral墙上还可以看见多少张海报。
输入输出格式
输入格式：
第一行： N M 分别表示electoral墙的长度和海报个数
接下来M行: Ai Bi 表示每张海报张贴的位置
输出格式：
输出贴完所有海报后，在electoral墙上还可以看见的海报数。
输入输出样例
输入样例#1：
100 5
1 4
2 6
8 10
3 4
7 10
输出样例#1：
4
说明
【约束条件】
1 0<= N <= 10000000 1<=M<=1000 1<= Ai <= Bi <=10000000
所有的数据都是整数。数据之间有一个空格
分析：这道题可以用线段树来做.
我一开始的思路是想要表示出每个区间的颜色，用二进制表示，可是m <= 1000......
既然静态统计答案不行，我就动态统计答案，每次看这个海报能不能贴上去，也就是看有没有空闲位置能被看到，后来发现如果这样的话，后来贴的小海报就不能被统计在答案中，所以倒着更新就好了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath> using namespace std; const int maxn = ; int n,m,a[],b[],c[maxn * ],ans,tag[maxn * ];
bool flag = false; void pushup(int o)
{
if (c[o * ] && c[o * + ])
c[o] = ;
} void build(int l,int r,int o)
{
if (l == r)
{
c[o] = ;
return;
}
int mid = (l + r) >> ;
build(l,mid,o * );
build(mid + ,r,o * + );
pushup(o);
} void pushdown(int o)
{
if (tag[o])
{
tag[o * ] = tag[o * + ] = tag[o];
tag[o] = ;
c[o * ] = c[o * + ] = ;
}
} void update(int l,int r,int o,int x, int y)
{
if (c[o])
return;
if (x <= l && r <= y)
{
flag = ;
c[o] = ;
tag[o] = ;
return;
}
pushdown(o);
int mid = (l + r) >> ;
if (x <= mid)
update(l,mid,o * ,x,y);
if (y > mid)
update(mid + ,r,o * + ,x,y);
pushup(o);
} int main()
{
scanf("%d%d",&n,&m);
build(,n,);
for (int i = ; i <= m; i++)
scanf("%d%d",&a[i],&b[i]);
for (int i = m; i >= ; i--)
{
flag = ;
update(,n,,a[i],b[i]);
if (flag == )
ans++;
}
printf("%d\n",ans); return ;
}