給定n張海報(bào)，每張海報(bào)的范圍從a[i]到b[i],依次覆蓋，后添加的海報(bào)會(huì)覆蓋掉原來(lái)位置的海報(bào)，求最后能夠看到幾張海報(bào)。多組數(shù)據(jù)。
1 5 1 4 2 6 8 10 3 4 7 10
4
首先離散化，然后用線段樹(shù)維護(hù)。注意題目里的起點(diǎn)和終點(diǎn)是線段，但是線段樹(shù)的操作是點(diǎn)，所以離散的時(shí)候要加入一些數(shù)。舉個(gè)例子來(lái)解釋一下：
[1,5]和[6,10]將[1,10]完全覆蓋 [1,4]和[6,10]不能將[1,10]完全覆蓋 在離散狀態(tài)下[1,4]和[6,10]是完全覆蓋的
這個(gè)時(shí)候如果在4和6之間加入一個(gè)數(shù)5，就可以解決問(wèn)題了。
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; //插入數(shù)字 sort(pt+1,pt+k+1);接下來(lái)就是每次對(duì)線段樹(shù)進(jìn)行覆蓋操作。
#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) //下傳標(biāo)記 { 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;} //區(qū)間覆蓋 pushdown(rt); //下傳標(biāo)記 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) //區(qū)間覆蓋情況 { 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; //插入數(shù)字 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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
