线段树典型例题--poj2528
此题的关键在于离散化。
对于线段(a,b)，要将a-1,a,b三个量都考虑进去。
否则我们看这样一个例子：
31 101 36 10答案是3
如果不考虑a-1，则答案会变成2。
【代码】
#include <iostream>#include <cstring>#include <string>#include <cstdio>#include <algorithm>using namespace std;const int N=10005;int a[N],b[N],col[N*10],g[N*3];bool v[N],pp[N*10];int ans,tot,n,cc;void down(int i){ if (!pp[i]) return; col[i*2]=col[i*2+1]=col[i]; pp[i*2]=pp[i*2+1]=true; pp[i]=false;}void ins(int i,int l,int r,int x,int y,int c){ if (x<=l && y>=r) { col[i]=c; pp[i]=true; return; } down(i); int mid=(l+r)>>1; if (x<=mid) ins(i*2,l,mid,x,y,c); if (y>mid) ins(i*2+1,mid+1,r,x,y,c); if (col[i*2]!=col[i*2+1] || col[i*2]==-1 || col[i*2+1]==-1) col[i]=-1;}int get(int i,int l,int r,int x){ if (col[i]!=-1) return col[i]; down(i); int mid=(l+r)>>1; if (x<=mid) return get(i*2,l,mid,x); else return get(i*2+1,mid+1,r,x);}int main(){ int i; freopen("in","r",stdin); scanf("%d",&cc); while (cc--) { memset(col,0,sizeof(col)); memset(pp,0,sizeof(pp)); memset(v,0,sizeof(v)); tot=ans=0; scanf("%d",&n); for (i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); g[tot++]=a[i]; g[tot++]=b[i]; if (a[i]>1) g[tot++]=a[i]-1; } sort(g,g+tot); tot=unique(g,g+tot)-g; for (i=1;i<=n;i++) { a[i]=lower_bound(g,g+tot,a[i])-g+1; b[i]=lower_bound(g,g+tot,b[i])-g+1; ins(1,1,tot,a[i],b[i],i); } for (i=1;i<=tot;i++) v[get(1,1,tot,i)]=true; for (i=1;i<=n;i++) ans+=v[i]; printf("%d\n",ans); }}