http://acm.hdu.edu.cn/showproblem.php?pid=1698

這是一個(gè)區(qū)間染色的問題，對(duì)于區(qū)間染色問題，通常的方法是在線段樹中定義一個(gè)cover域，當(dāng)cover的值為-1的時(shí)候，則表示這個(gè)線段的覆蓋不是有一個(gè)顏色染成的，其中包含了多種顏色，而當(dāng)cover為一個(gè)非-1的值時(shí)，例如cover==1時(shí)表示該線段是有第一種顏色染成的。 對(duì)于這題，由于是成段成段的在跟新線段樹，我們自然不能簡(jiǎn)單的遞歸到根節(jié)點(diǎn)再進(jìn)行處理，這樣毫無疑問是要超時(shí)的，所以我們只能成段的跟新。

那么，如何做到成段的跟新呢？這里需要運(yùn)用一種叫著lazy的思想，lazy顧名思義便是懶惰的意思。該思想大概的意思便是：假設(shè)要跟新區(qū)間[a，b]，那么當(dāng)我們找到區(qū)間[a，b]時(shí)，便不再往下進(jìn)行遞歸，而是在該區(qū)間上標(biāo)記上一個(gè)lazy，表示這里有信息需要向下傳遞。那么當(dāng)我們需要跟新區(qū)間[a,b/2]時(shí)，我們便一定會(huì)從區(qū)間[a,b]經(jīng)過，經(jīng)過的過程中，我們發(fā)現(xiàn)區(qū)間[a,b]有信息需要向下傳遞，此時(shí)便將區(qū)間[a,b]的信息傳遞給其子區(qū)間。這樣在必要的時(shí)候才一層一層的傳遞，便節(jié)約了很多時(shí)間。具體見程序吧，很清晰的

View Code 1 #include<iostream>
2 #include<string>
3 using namespace std;
4
5 struct node
6 {
7 int l;
8 int r;
9 int cover;
10 };
11
12 node tree[500000];
13 int n,m;
14
15 void build(int i,int l,int r)
16 {
17 tree[i].l=l;
18 tree[i].r=r;
19 tree[i].cover=1; //初始顏色為1
20 if(l==r)
21 return;
22 int mid=(l+r)/2;
23 build(2*i,l,mid);
24 build(2*i+1,mid+1,r);
25 }
26
27 void updata(int i,int l,int r,int w)
28 {
29 if(tree[i].l>r || tree[i].r<l)
30 return;
31 if(tree[i].l>=l && tree[i].r<=r)
32 {
33 tree[i].cover=w; //cover表示lazy標(biāo)記，當(dāng)cover的值不為-1的時(shí)候，就說明該區(qū)間有信息需要向下傳遞
34 return;
35 }
36 if(tree[i].cover!=-1) //該區(qū)間有信息需要傳遞
37 {
38 tree[2*i].cover=tree[2*i+1].cover=tree[i].cover; //將其標(biāo)記傳遞給子區(qū)間
39 tree[i].cover=-1; //同時(shí)自身取消標(biāo)記
40 }
41 updata(2*i,l,r,w);
42 updata(2*i+1,l,r,w);
43 }
44
45 int ans;
46 void find(int i)
47 {
48 if(tree[i].cover!=-1) //單色區(qū)間，直接取其值
49 {
50 ans+=(tree[i].r-tree[i].l+1)*tree[i].cover;
51 return;
52 }
53 if(tree[i].l==tree[i].r)
54 return;
55 find(2*i); //非單色區(qū)間，則向下遞歸
56 find(2*i+1);
57 }
58
59 int main()
60 {
61 int cas,i,a,b,c,o=1;
62 freopen("in.txt","r",stdin);
63 scanf("%d",&cas);
64 while(cas--)
65 {
66 scanf("%d%d",&n,&m);
67 build(1,1,n);
68 for(i=0;i<m;i++)
69 {
70 scanf("%d%d%d",&a,&b,&c);
71 updata(1,a,b,c);
72 }
73 ans=0;
74 find(1);
75 printf("Case %d: The total value of the hook is %d.\n",o++,ans);
76 }
77 return 0;
78 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/ka200812/archive/2011/11/09/2242248.html

與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的线段树专辑——hdu 1698 Just a Hook的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。