【POJ 2528】Mayor's posters

2019-11-14 09:23:16

字體：大中小

來源：轉載

供稿：網友

POJ2528

題意

給定n張海報，每張海報的范圍從a[i]到b[i],依次覆蓋，后添加的海報會覆蓋掉原來位置的海報，求最后能夠看到幾張海報。多組數據。

樣例輸入

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

樣例輸出

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

接下來就是每次對線段樹進行覆蓋操作。

#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;}

上一篇：tjdsc

下一篇：java AtomicInteger 源碼之CAS