POJ.2528 Mayor’s posters (线段树 区间更新 区间查询 离散化)
题意分析
贴海报，新的海报能覆盖在旧的海报上面，最后贴完了，求问能看见几张海报。
最多有10000张海报，海报左右坐标范围不超过10000000。
一看见10000000肯定就要离散化了，因为建树肯定是建不下。离散化的方法是：先存到一个数组里面，然后sort，之后unique去重，最后查他离散化的坐标lower_bound就行了。特别注意如果是从下标为0开始存储，最后结果要加一。多亏wmr神犇提醒。
这题是覆盖问题。如果正向考虑，后者就可以覆盖在前者之上；如果逆向考虑，就是前者不能涂在后者之上。这里采用逆向考虑的方法。
具体实现细节是，我们按照给出的顺序逆向枚举，将查询和更新一体化，如果按照给出的区间查询到某个地方，发现没有涂色，那说明这张海报一定可以看见，反之不能被看见，根据每次查询的结果，来决定计数器是否自增。
代码总览
#include <cstdio>
#include <cstring>
#include <algorithm>
#define nmax 10005
using namespace std;
struct Tree{
int l,r;
//int val;
bool iscover;
int mid(){
return (l+r)>>1;
}
};
Tree tree[nmax<<4];
struct point{
int l;
int r;
}p[nmax<<1];
int finalpos[nmax<<1];
bool flag = false;
int ans = 0;
void PushUp(int rt)
{
tree[rt].iscover = tree[rt<<1].iscover && tree[rt<<1|1].iscover;
}
void Build(int l, int r, int rt)
{
tree[rt].l = l; tree[rt].r = r;
tree[rt].iscover = false;
if(l == r){
return;
}
Build(l,tree[rt].mid(),rt<<1);
Build(tree[rt].mid()+1,r,rt<<1|1);
}
void Query(int l,int r,int rt)
{
if(tree[rt].iscover) return;
if(l>tree[rt].r || r<tree[rt].l) return ;
if(tree[rt].l == tree[rt].r){
if(!tree[rt].iscover){
tree[rt].iscover = true;
flag = true;
}
return;
}
//PushDown(rt);
//if(l <= tree[rt].l && tree[rt].r <= r) return tree[rt].val;
Query(l,r,rt<<1) , Query(l,r,rt<<1|1);
PushUp(rt);
}
int t,n;
int tag = 0;
void discretization()
{
tag = 0;
for(int i = 0;i<n;++i){
scanf(" %d %d",&p[i].l,&p[i].r);
finalpos[tag++] = p[i].l;
finalpos[tag++] = p[i].r;
}
sort(finalpos,finalpos+tag);
tag = unique(finalpos,finalpos+tag) - finalpos;
}
int main()
{
//freopen("in2528.txt","r",stdin);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
discretization();
Build(1,nmax<<2,1);
ans = 0;
for(int i = n-1; i>=0;--i){
flag = false;
int a = lower_bound(finalpos,finalpos+tag,p[i].l) - finalpos+1;
int b = lower_bound(finalpos,finalpos+tag,p[i].r) - finalpos+1;
Query(a,b,1);
if(flag) ans++;
}
printf("%d\n",ans);
}
return 0;
}