poj 2528 Mayor's posters
题目链接：
http://poj.org/problem?id=2528
思路：
线段树+离散化技巧（这里的离散化需要注意一下啊，题目数据弱看不出来）
假设给出：
1~10
1~4
7-10
最后可以看见三张海报
如果离散化的时候不注意，就会变成
1 4 7 10（原始）
1 2 3 4 （离散化）
转化为：
1~4
1~2
3~4
这样的话最后只能看见两张海报
解决办法，如果原数据去重排序后相互之间差值大于1，则在他们之间再插入一个数值，使得大于前者小于后者即可
我感觉这道题目用线段树还不够快，因为最后查询，遍历了整整一棵树...
代码：
#include <iostream>
#include <stdio.h>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 10000005;
struct node {
int l,r,color,lazy;
inline void update(int val) {
color=val;
lazy=val;
}
} tr[maxn*4];
int a[maxn],b[maxn],c[maxn*2];
set<int> se;
inline void push_down(int s) {
int lazyval = tr[s].lazy;
if(!lazyval) return;
tr[s<<1].update(lazyval);
tr[s<<1|1].update(lazyval);
tr[s].lazy=0;
}
void build(int s, int l, int r) {
tr[s].l=l;tr[s].r=r;
tr[s].lazy=tr[s].color=0;
if(l==r) return;
int mid=(l+r)>>1;
build(s<<1,l,mid);
build(s<<1|1,mid+1,r);
}
void update(int s, int l, int r, int color) {
if(tr[s].l==l&&tr[s].r==r) {
tr[s].update(color);
return;
}
push_down(s);
int mid=(tr[s].l+tr[s].r)>>1;
if(r<=mid) update(s<<1,l,r,color);
else if(l>mid) update(s<<1|1,l,r,color);
else {
update(s<<1,l,mid,color);
update(s<<1|1,mid+1,r,color);
}
}
void query(int s) {
if(tr[s].l==tr[s].r) {
if(!tr[s].color) return;
se.insert(tr[s].color);
return;
}
push_down(s);
query(s<<1);
query(s<<1|1);
}
inline void init() {
se.clear();
}
int main() {
int t,m,tot,index;
scanf("%d",&t);
while(t--) {
init();
tot=1;
scanf("%d",&m);
for(int i=1;i<=m;++i) {
scanf("%d %d",&a[i],&b[i]);
c[tot]=a[i];++tot;
c[tot]=b[i];++tot;
}
/*离散化开始*/
index=tot;
--tot;
sort(c+1,c+index);
for(int i=2;i<=tot;++i) {
if(c[i]-c[i-1]>1) {
c[index]=c[i-1]+1;
index++;
}
}
sort(c+1,c+index);
tot=unique(c+1,c+index)-c;
--tot;
build(1,1,tot);
for(int i=1;i<=m;++i){
a[i]=lower_bound(c+1,c+tot+1,a[i])-(c+1)+1;
b[i]=lower_bound(c+1,c+tot+1,b[i])-(c+1)+1;
update(1,a[i],b[i],i);
}
/*离散化完成*/
query(1);
printf("%d
",se.size());
}
return 0;
}