POJ2528

题意

给定n张海报，每张海报的范围从a[i]到b[i],依次覆盖，后添加的海报会覆盖掉原来位置的海报，求最后能够看到几张海报。多组数据。

样例输入

1 5 1 4 2 6 8 10 3 4 7 10

样例输出

4

---

sol

首先离散化，然后用线段树维护。注意题目里的起点和终点是线段，但是线段树的操作是点，所以离散的时候要加入一些数。举个例子来解释一下：

[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);

PS附上一份区间和的tag写法，上次tag更新写反了一次竟然！

void pushdown() { sum[rt<<1] += tag[rt] * siz[rt<<1]; sum[rt<<1|1] += tag[rt] * siz[rt<<1|1]; tag[rt<<1] += tag[rt]; tag[rt<<1|1] += tag[rt]; tag[rt] = 0; } void update(int rt,int l,int r,int L,int R,int d) { if (L <= l && r <= R) {sum[rt] += d * siz[rt]; tag[rt] += d; return;} pushdown(); int mid = (l + r) >> 1; if (L <= mid) update(rt<<1,l,mid,L,R,d); if (mid < R) update(rt<<1|1,mid+1,r,L,R,d); sum[rt] = sum[rt<<1] + sum[rt<<|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 120000 using 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; }