題意：

在1~10000000這個區間中讀取n個海報的區間信息，后面的海報會覆 蓋前面的海報，問最后能看到幾張海報.（本題是一道bug題下面會提）

題目：

The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:?

• Every candidate can place exactly one poster on the wall.?
• All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).?
• The wall is divided into segments and the width of each segment is one byte.?
• Each poster must completely cover a contiguous number of wall segments.

They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.?
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.?

Input

The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l?i?and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l?i?<= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l?i, l?i+1 ,... , ri.

Output

For each input data set print the number of visible posters after all the posters are placed.?

The picture below illustrates the case of the sample input.?

Sample Input

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

Sample Output

4

分析

分析：先離散化、再線段樹。

【1】離散化，把無限空間中有限的個體映射到有限的空間中去，以此提高算法的時空效率。
? ? ? ? ?數據的離散化有些數據本身很大， 自身無法作為數組的下標保存對應的屬性。如果這時只是需要這堆數據的相對屬性， 那? ? ? ? ? ?么可以對其進行離散化處理。當數據只與它們之間的相對大小有關，而與具體是多少無關時，可以進行離散化。

（1）離散化，將所有出現過的點存儲在排序，然后去掉相同的點。如下面的例子 （題目的樣例），因為單位1是一個單位長度，將下面的

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

? ? ? —? —? —? —? —? —? —? — ?????

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

離散化? X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] = 8; X[8] = 10

于是將一個很大的區間映射到一個較小的區間之中了，然后再對每一張海報依 次更新在寬度為1~8的墻上(用線段樹），最后統計不同顏色的段數。

1.先把每條線段的單獨存下來，同時把每個端點的值存在另一個數組里， 在此把圖放上for(int i=1; i<=m; i++){scanf("%d%d",&a[i],&b[i]);c[k++]=a[i];c[k++]=b[i];} 2.來一發排序，sort即可，線段樹是以點的形式存儲了線段，所以難免會有局限，（在這里我們只看點，其實 是有問題的，正確著做反而是錯誤的，因為若【2,3】，【4,5】，線段樹只對點操作，認為是連續的，實際 不連續，所有應該兩次sort，第一次需判斷兩點之間是否間隔為一，若是在兩點之間加一個數，第二次sort 去重。）sort(c,c+k); 3.然后把數組中重復的元素去掉，因為接下來我們要用線段樹查找來確定每條線段的標號， 去重才能保證標號唯一。for(int i=0; i<k; i++){if(c[i]!=c[i+1])d[c[i]]=++tot;} #include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int M=1e4+10;//線段樹開4倍空間 const int N=1e7+10; int a[M],b[M],c[M*2],d[N],dp[M*8],add[M*8],book[M*2],ans; void dfs(int o) {if(add[o])//懶惰標記下移{add[o<<1]=add[o<<1|1]=add[o];dp[o<<1]=dp[o<<1|1]=add[o];add[o]=0;} } void update(int o,int l,int r,int x,int y,int c)//區間更新 {if(x<=l&&y>=r)/*對值覆蓋*/{add[o]=c;dp[o]=c;return ;}dfs(o);int mid=(r+l)>>1;if(x<=mid)update(o<<1,l,mid,x,y,c);if(y>mid)update(o<<1|1,mid+1,r,x,y,c); } void query(int o,int l,int r) {if(l==r){if(!book[dp[o]]){ans++;book[dp[o]]=1;}return ;}dfs(o);int mid=(l+r)>>1;query(o<<1,l,mid);query(o<<1|1,mid+1,r); } int main() {int t;scanf("%d",&t);while(t--){int m,k=0,tot=0;memset(book,0,sizeof(book));memset(add,0,sizeof(add));scanf("%d",&m);for(int i=1; i<=m; i++){scanf("%d%d",&a[i],&b[i]);c[k++]=a[i];c[k++]=b[i];}sort(c,c+k);/*排序操作,目的去重*/for(int i=0; i<k; i++){if(c[i]!=c[i+1]) /*離散化操作,去重*/d[c[i]]=++tot;}for(int i=1; i<=m; i++){int x=d[a[i]];int y=d[b[i]];update(1,1,tot,x,y,i);//由于每次的海報不同所以直接給海報一個編號}ans=0;query(1,1,tot);printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的Mayor's posters POJ - 2528 （离散化+线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。