给定n张海报，每张海报的范围从a[i]到b[i],依次覆盖，后添加的海报会覆盖掉原来位置的海报，求最后能够看到几张海报。多组数据。
1 5 1 4 2 6 8 10 3 4 7 10
4
首先离散化，然后用线段树维护。注意题目里的起点和终点是线段，但是线段树的操作是点，所以离散的时候要加入一些数。举个例子来解释一下：
[1,5]和[6,10]将[1,10]完全覆盖 [1,4]和[6,10]不能将[1,10]完全覆盖 在离散状态下[1,4]和[6,10]是完全覆盖的
这个时候如果在4和6之间加入一个数5，就可以解决问题了。
for (i = 1;i <= n; i++) { scanf("%d%d",&lp[i],&rp[i]); pt[++k] = lp[i]; pt[++k] = rp[i]; }sort(pt+1,pt+k+1); k = 0;for (i = 1;i <= n * 2; i++)if (pt[i] != pt[i-1]) pt[++k] = pt[i]; //排序去重 for (i = k;i >= 2; i--)if (pt[i] - pt[i-1] != 1) pt[++k] = pt[i-1] + 1; //插入数字 sort(pt+1,pt+k+1);接下来就是每次对线段树进行覆盖操作。
#include<cmath>#include<cstdio>#include<vector>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 120000using namespace std;int T,n,k,i,res;int lp[N],rp[N],pt[N*3],col[N<<4];bool hash[N];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 mid = (l + r) >> 1; if (L <= mid) update(L,R,c,l,mid,rt << 1); if (mid < R) update(L,R,c,mid+1,r,rt << 1 | 1);}void query(int l,int r,int rt){ if (col[rt] != -1) //区间覆盖情况 { if (hash[col[rt]] == false) res++; hash[col[rt]] = true; return; } if (l == r) return; int mid = (l + r) >> 1; query(l,mid,rt << 1); query(mid+1,r,rt << 1 | 1);}int search(int x) //二分搜索 { int l = 1,r = k; while (l <= r) { int mid = (l + r) >> 1; if (x == pt[mid]) return mid; if (x < pt[mid]) r = mid - 1; else l = mid + 1; } return -1;}int main(){ cin>>T; while (T--) { cin>>n; k = 0; for (i = 1;i <= n; i++) { scanf("%d%d",&lp[i],&rp[i]); pt[++k] = lp[i]; pt[++k] = rp[i]; } sort(pt+1,pt+k+1); k = 0; for (i = 1;i <= n * 2; i++) if (pt[i] != pt[i-1]) pt[++k] = pt[i]; //排序去重 for (i = k;i >= 2; i--) if (pt[i] - pt[i-1] != 1) pt[++k] = pt[i-1] + 1; //插入数字 sort(pt+1,pt+k+1); memset(col,-1,sizeof(col)); for (i = 1;i <= n; i++) { int l = search(lp[i]); int r = search(rp[i]); //二分搜索位置 update(l,r,i,1,k,1); } res = 0; memset(hash,false,sizeof(hash)); query(1,k,1); cout<<res<<endl; } return 0;}新闻热点
疑难解答
