線段樹重溫——刷墻
描述
在一面很長的墻壁上，工人們用不同的油漆去刷墻，然而可能有些地方刷過以后覺得不好看，他們會重新刷一下。有些部分因為重復刷了很多次覆蓋了很多層油漆，toshio很好奇那些地方被刷過多少種顏色的油漆。輸入若干行輸入，每行兩個數字B[i],E[i](0<=B[i]<=E[i]<=200000)表示這次刷的墻壁是哪一段（假設每次刷的時候油漆顏色都和之前的不同），以0 0結束
又若干行輸入，每行兩個數字begin[i],end[i]（0<=begin[i]<=end[i]<=200000）表示toshio詢問的段，以0 0結束輸出對于每個toshio的詢問輸出(end[i]-begin[i]+1)行,表示對應詢問段的每個點被多少種顏色的油漆覆蓋過。
樣例輸入
1 20
5 10
10 20
0 0
4 6
10 11
0 0
樣例輸出
1
2
2
3
關鍵點1：
在這里要提醒大家一下，我們要開開的結構體數目得
是線段的最大長度的至少3倍，一般開到4倍。注意一
下這點就行了，不然的話，你連輸入就過不了，更別
說得到正確的結果了。
關鍵點2：
另外，線段樹是以段為單位的，這個怎么理解呢？
以
if(Tree[level].left==left && Tree[level].right==right)
Tree[level].icount += 1;
這句話來說，假如left=1, right=5時，
那么，從1到5的這個段上的1，2，3，4，5中的icount值
都是作了Tree[level].icount += 1;這個動作。
View Code
#include<iostream> #include<cstdio> using namespace std; struct Node { int left; int right; int mid; int icount; }; Node Tree[2000000]; void BuildTree(int level, int left, int right) { Tree[level].icount=0; Tree[level].left = left; Tree[level].right = right; Tree[level].mid = (left+right)/2; if(left==right) return; else { BuildTree(2*level, left, Tree[level].mid); ///建立左子結點 BuildTree(2*level+1, Tree[level].mid+1, right); ///建立右子結點 } } void Insert(int level, int left, int right) //統計經過每個點的次數 { if(Tree[level].left==left && Tree[level].right==right) //if語句是在區間吻合時起作用的，這時恰好要是結束的時候。 Tree[level].icount += 1; else if(left > Tree[level].mid) //往右邊進行搜索(這是被搜索的區間完全落在右邊的情況) Insert(2*level+1, left, right); else if(right <= Tree[level].mid) //往左邊進行搜索(這是被搜索的區間完全落在左邊的情況) Insert(2*level, left, right); else //往兩邊進行搜索(這是被搜索的區間落在兩邊的情況，所以要向兩邊同時進行搜索) { Insert(2*level, left, Tree[level].mid); Insert(2*level+1, Tree[level].mid+1, right); } } int Find(int level, int target) //對不同的區間進行遍歷查詢 { if(target==Tree[level].left && target==Tree[level].right) return Tree[level].icount; else if(target > Tree[level].mid) return Tree[level].icount+Find(2*level+1, target); else if(target <= Tree[level].mid) return Tree[level].icount+Find(2*level, target); } int main() { int left, right; BuildTree(1, 0, 200000); while(cin>>left>>right && (left+right)) Insert(1, left, right); while(cin>>left>>right && (left+right)) for(int i=left; i<=right; i++) cout<<Find(1, i)<<endl; return 0; }
posted on 2011-10-01 14:45 More study needed. 閱讀(407) 評論(0) 收藏 舉報
浙公網安備 33010602011771號