按照输入次序进行覆盖，求最上面能看到多少种不同的海报，一看就是线段树加离散化，不过这里的离散化需要注意
例如 测试用例的为
3
1 9
1 3
6 9
这样的话普通的离散化 如下
1 2 3 4
1 3 6 9
上面对应离散化编号，下面则是实际的值，这样的话普通离散化算出的答案是2，而正确的答案是3
所以 针对这种情况，我们约定：当离散化后的相邻点的坐标差大于1时，在这两个离散点之间，插入两坐标之间的任意的一个值。
对于上述测试用例，按约定的离散化可得，
1 2 3 4 5 6 7
1 2 3 4 6 7 9
这样进行离散化得到的答案就为3，代码如下
/* Problem: 2528 User: 96655 Memory: 1368K Time: 94MS Language: G++ Result: Accepted */ #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include <algorithm> #include<cstring> using namespace std; const int maxn=40005; short a[maxn<<2],ans; bool b[maxn<<2],xx[10005]; struct Q { int l,r; } q[10005]; int y[maxn]; void pushdown(int rt) { if(b[rt]) { b[rt*2]=b[rt*2+1]=1; a[rt*2]=a[rt*2+1]=a[rt]; b[rt]=0; } } void update(int rt,int l,int r,int x,int y,int c) { if(x<=l&&r<=y) { a[rt]=c; b[rt]=1; return; } int m=(l+r)>>1; pushdown(rt); if(x<=m)update(rt*2,l,m,x,y,c); if(y>m)update(rt*2+1,m+1,r,x,y,c); } void query(int rt,int l,int r) { if(l==r) { if(a[rt]==-1)return; if(!xx[a[rt]]) ++ans,xx[a[rt]]=1; return; } int m=(l+r)>>1; pushdown(rt); query(rt*2,l,m); query(rt*2+1,m+1,r); } int main() { int T; scanf("%d",&T); while(T--) { int n,cnt=0,d=1; ans=0; scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d%d",&q[i].l,&q[i].r); y[cnt++]=q[i].l; y[cnt++]=q[i].r; } sort(y,y+cnt); for(int i=1; i<cnt; ++i) if(y[i]!=y[i-1])y[d++]=y[i]; for (int i=d-1; i>0; --i) if(y[i]-1>y[i-1])y[d++]=y[i]-1; sort(y,y+d); memset(a,-1,sizeof(a)); memset(b,0,sizeof(b)); memset(xx,0,sizeof(xx)); for(int i=1; i<=n; ++i) { q[i].l=lower_bound(y,y+d,q[i].l)-y; ++q[i].l; q[i].r=lower_bound(y,y+d,q[i].r)-y; ++q[i].r; update(1,1,d,q[i].l,q[i].r,i); } query(1,1,d); printf("%d ",ans); } return 0; }