poj 2528 Mayor‘s posters （线段树）

题意：
给一段长度为10000000的墙贴海报，海报有一个覆盖的范围，后贴的海报可以覆盖先贴的海报。最后询问我们墙上有多少海报显示出来。
题解：
很明显，区间范围太大，直接用线段树的话会超时，我们可以离散化区间，
例如：1~4，4 ~ 8, 1 ~ 8, lsh[1]=1,lsh[2]=4;,lah[3]=8; 那么第一次贴的范围就是1 ~2 ，第二次就是 2 ~3 ，第三次就是 1 ~ 3，最后答案就是1。但是这么离散化是有缺陷的，例如 1 ~8 ，1 ~ 4 ，6 ~8 ，lah[1]=1,lsh[2]=4, lsh[3]=6, lah[4]=8,第一次贴的范围是 1 ~ 4，第二次就是 1 ~ 2，第三次就是 3 ~ 4，这样算出来的答案是2，但实际答案却是 3，所以我们要在范围之差大于1 的元素中再添加一个元素。上面例子就是要在 4和6中再添加一个5（当然还要添加其他的）。离散化之后就可以线段树维护了。
代码：

#include<cstdio>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<stack>
#include<set>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int MAXN=1e5+5;
int lsh[MAXN];
int lt[MAXN];
int rt[MAXN];
int vis[MAXN];
struct Node
{int l;int r;int sum;
}node[MAXN<<2];
void push_down(int num)
{node[num<<1].sum=node[num].sum;node[num<<1|1].sum=node[num].sum;node[num].sum=-1;
}
void build(int left,int right,int num)
{node[num].l=left;node[num].r=right;node[num].sum=-1;if(left==right){return;}int mid=(left+right)/2;build(left,mid,num<<1);build(mid+1,right,num<<1|1);
}
void updata(int left,int right,int val,int num)
{if(node[num].l>=left&&node[num].r<=right){node[num].sum=val;return;}if(node[num].sum!=-1){push_down(num);}int mid=(node[num].l+node[num].r)>>1;if(right<=mid){updata(left,right,val,num<<1);}else if(left>mid){updata(left,right,val,num<<1|1);}else{updata(left,mid,val,num<<1);updata(mid+1,right,val,num<<1|1);}
}
int ans;
void query(int num)
{if(node[num].sum!=-1&&!vis[node[num].sum]){ans++;vis[node[num].sum]=1;return;}if(node[num].l==node[num].r) return;if(node[num].sum!=-1){push_down(num);}//int mid=(node[num].l+node[num].r)/2;query(num<<1);query(num<<1|1);
}
int main()
{int n;int t;scanf("%d",&t);while(t--){memset(vis,0,sizeof vis);ans=0;scanf("%d",&n);int tot=0;for(int i=1;i<=n;i++){scanf("%d %d",&lt[i],&rt[i]);lsh[++tot]=lt[i];lsh[++tot]=rt[i];}sort(lsh+1,lsh+1+tot);int pos=unique(lsh+1,lsh+1+tot)-lsh;int tt=pos-1;for(int i=2;i<=pos-1;i++){if(lsh[i]-lsh[i-1]>1){lsh[++tt]=lsh[i-1]+1;}}sort(lsh+1,lsh+1+tt);build(1,tt,1);for(int i=1;i<=n;i++){int p1=lower_bound(lsh+1,lsh+1+tt,lt[i])-lsh;int p2=lower_bound(lsh+1,lsh+1+tt,rt[i])-lsh;updata(p1,p2,i,1);}query(1);printf("%d\n",ans);}
}