poj2528 发表于 2018-04-07 | 分类于 算法 , 数据结构 , 线段树 | 阅读数 次 链接:poj2528 题解 线段树+离散化,注意离散化的时候在相邻距离大于1的点之间要插入一个点,避免覆盖问题,比如1-10 1-4 6-10 如果不加点,答案 是2,显然不正确 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#define rep(i,x,y) for(register int i=x;i<=y;++i)#define repd(i,x,y) for(register int i=x;i>=y;--i)using namespace std;const int N=1e6;int hash[N],rt[N<<2],x[N],y[N],a[N],n,nn,m,T,ans;void pushdown(int o){rt[o<<1]=rt[o<<1|1]=rt[o];rt[o]=-1;}void update(int o,int l,int r,int ll,int rr,int c){ if(ll<=l&&rr>=r){rt[o]=c;return ;} if(rt[o]!=-1)pushdown(o); int mid=l+r>>1; if(ll<=mid)update(o<<1,l,mid,ll,rr,c); if(rr>mid)update(o<<1|1,mid+1,r,ll,rr,c);}void query(int o,int l,int r){ if(l==r){if(rt[o]!=-1&&!hash[rt[o]])ans++,hash[rt[o]]=1;return ;} if(rt[o]!=-1)pushdown(o); int mid=l+r>>1; query(o<<1,l,mid); query(o<<1|1,mid+1,r);}int ask(int c){ int l=1,r=m; while(l<r){ int mid=l+r>>1; if(a[mid]==c)return mid; if(a[mid]<c)l=mid+1; else r=mid-1; } return l;}int main(){ scanf("%d",&T); while(T--){ m=1;ans=nn=0; memset(hash,0,sizeof(hash)); memset(rt,-1,sizeof(rt)); scanf("%d",&n); rep(i,1,n){scanf("%d%d",&x[i],&y[i]);a[++nn]=x[i];a[++nn]=y[i];} sort(a,a+nn); rep(i,2,nn-1)if(a[i]!=a[i-1])a[++m]=a[i]; repd(i,m,1)if(a[i]-a[i-1]>1)a[++m]=a[i]-1; sort(a+1,a+m+1); rep(i,1,n){ int l=ask(x[i]); int r=ask(y[i]); update(1,1,m,l,r,i); } query(1,1,m); printf("%d\n",ans); } return 0;}