题目链接
点击打开链接
这一题可以算是我写的时间最长的一题了。。。。
为啥呢， 因为我刚开始写水题时候就无意看见这一题，，，果断暴力，，，死翘翘，，
然后没一点思路，根本不会写。所以放在哪，一直都没写。。。。
最近在写线段树专题，，又碰上这题，，，，这次不能在放过了。
题意：
一个无限长度的墙，有n个人往墙上贴海报，给出每个人贴海报的位置，和先后顺序。问最后墙上能看见多少海报。（被覆盖就看不见）
题解：
首先墙太长了，，，，要用离散化，比如 1 123 10000 2130000000
可以映射成 1 2 3 4
这样的话可以有效的减小数据大小。
但是我看大神的解法（好像是kuangbin大神，因为我写的是kuangbin带你飞专题，，） 说离散化直接对应会有错误，
例如：
1-10 1-4 5-10
1-10 1-4 6-10
他的解决方法是如果相邻两个数字间距大于1 的话再补上一个数字。
然后按照顺序更新海报墙。 upda 成段更新数据。
最后查询，使用一个简单hash。
//#include<bits/stdc++.h> #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #define maxn 11111 #define LL long long using namespace std; int li[maxn],ri[maxn]; int a[maxn*4],col[maxn<<4],ans; bool Hash[maxn]; void Pushdown(int rt){ if(col[rt]!=-1){ col[rt<<1]=col[rt<<1|1]=col[rt]; col[rt]=-1; } } void update(int L,int R,int c,int l,int r,int rt){ if(L<=l&&r<=R){ col[rt]=c; return ; } Pushdown(rt); int m=(l+r)>>1; if(L<=m) update(L,R,c,l,m,rt<<1); if(R>m) update(L,R,c,m+1,r,rt<<1|1); } void query(int l,int r,int rt){ if(col[rt]!=-1){ if(!Hash[col[rt]]) ans++; Hash[col[rt]]=true; return ; } if(l==r) return ; int m=(l+r)>>1; query(l,m,rt<<1); query(m+1,r,rt<<1|1); } int lookup(int key,int n,int x[]){ int l=0,r=n-1; while(l<=r){ int m=(l+r)>>1; if(x[m]==key) return m; if(x[m]<key) l=m+1; else r=m-1; } return -1; } int main(){ int T,n; scanf("%d",&T); while(T--){ ans=0; scanf("%d",&n); int cou=0,con=1; for(int i=0;i<n;i++){ scanf("%d%d",&li[i],&ri[i]); a[cou++]=li[i]; a[cou++]=ri[i]; } sort(a,a+cou); for(int i=1;i<cou;i++) if(a[i]!=a[i-1]) a[con++]=a[i]; for(int i=con-1;i>0;i--) if(a[i]!=a[i-1]+1) a[con++]=a[i-1]+1; sort(a,a+con); memset(col,-1,sizeof(col)); for(int i=0;i<n;i++){ int l=lookup(li[i],con,a); int r=lookup(ri[i],con,a); update(l,r,i,0,con,1); } memset(Hash,false,sizeof(Hash)); query(0,con,1); printf("%d\n",ans); } return 0; }