http://poj.org/problem?id=2482

A了這題后，我就在想，是不是ACMER都找不到女朋友.....

這題看似很新穎，其實(shí)就是求線段樹區(qū)間最值。所謂區(qū)間最值，其實(shí)就是和RMQ差不多，只不過RMQ是以點(diǎn)為單位，而這個(gè)是以區(qū)間為單位。

怎么扯到區(qū)間最值了呢？

因?yàn)槊恳活w星星，它都有一個(gè)亮度，假設(shè)這個(gè)星星現(xiàn)在正在最左邊，那么它的亮度將會(huì)影響到向右W的范圍。也就是說[star.x，star.x+W]這個(gè)區(qū)間都會(huì)因?yàn)檫@個(gè)亮度的影響而加上這個(gè)亮度值，最后求一個(gè)[x,x+W]的區(qū)間，并且該區(qū)間的亮度最大，這就是區(qū)間最值！方法和RMQ一樣，只是不是更新到節(jié)點(diǎn)，而是更新到相應(yīng)線段即可！

這里還要注意的幾個(gè)地方

1、是這個(gè)題目要求恰好在窗戶上的星星是不算數(shù)的，所以我們?nèi)^(qū)間[x,x+W]的時(shí)候，應(yīng)該取[x,x+W-1]

2、必須離散化

3、注意高度上的要求，當(dāng)最高的和最低的那顆星星的高度差等于或者超過H以后，我們就要減去最低的那顆星星亮度，因?yàn)榇皯舾叨仁怯邢薜?#xff01;

?

總的來說，就是不容易看出其數(shù)學(xué)模型，看出來后就很簡單了

?

View Code 1 #include<iostream>
2 #include<string>
3 #include<algorithm>
4 using namespace std;
5
6 struct node
7 {
8 int l;
9 int r;
10 __int64 add;
11 __int64 max_val;
12 };
13
14 node tree[100000];
15 int n,len;
16 __int64 H,W;
17 __int64 xx[20001];
18
19 struct star
20 {
21 __int64 x,y,c;
22 };
23
24 star num[10001];
25
26 int cmp(star a,star b)
27 {
28 return a.y<b.y;
29 }
30
31 int find(__int64 x)
32 {
33 int l=0,r=len,mid;
34 while(l<=r)
35 {
36 mid=(l+r)/2;
37 if(xx[mid]==x)
38 return mid;
39 if(xx[mid]<x)
40 l=mid+1;
41 else
42 r=mid-1;
43 }
44 return l;
45 }
46
47 void build(int i,int l,int r)
48 {
49 tree[i].l=l;
50 tree[i].r=r;
51 tree[i].add=0;
52 tree[i].max_val=0;
53 if(l==r)
54 return;
55 int mid=(l+r)/2;
56 build(2*i,l,mid);
57 build(2*i+1,mid+1,r);
58 }
59
60 void updata(int i,int l,int r,__int64 c)
61 {
62 if(tree[i].l>r || tree[i].r<l)
63 return;
64 if(tree[i].l>=l && tree[i].r<=r)
65 {
66 tree[i].add+=c;
67 tree[i].max_val+=c;
68 return;
69 }
70 if(tree[i].add)
71 {
72 tree[2*i].add+=tree[i].add;
73 tree[2*i+1].add+=tree[i].add;
74 tree[2*i].max_val+=tree[i].add;
75 tree[2*i+1].max_val+=tree[i].add;
76 tree[i].add=0;
77 }
78 updata(2*i,l,r,c);
79 updata(2*i+1,l,r,c);
80 tree[i].max_val=tree[2*i].max_val>tree[2*i+1].max_val?tree[2*i].max_val:tree[2*i+1].max_val;
81 }
82
83 int main()
84 {
85 int i,j,m,a,b;
86 freopen("in.txt","r",stdin);
87 while(scanf("%d%I64d%I64d",&n,&W,&H)!=EOF)
88 {
89 m=0;
90 for(i=0;i<n;i++)
91 {
92 scanf("%I64d%I64d%I64d",&num[i].x,&num[i].y,&num[i].c);
93 xx[m++]=num[i].x;
94 xx[m++]=num[i].x+W;
95 }
96 sort(xx,xx+m);
97 len=1;
98 for(i=1;i<m;i++)
99 {
100 if(xx[i-1]!=xx[i])
101 xx[len++]=xx[i];
102 }
103 len--;
104 build(1,0,len);
105 sort(num,num+n,cmp);
106 __int64 ans=0;
107 for(j=0,i=0;i<n;i++)
108 {
109 while(num[i].y-num[j].y>=H) //控制高度范圍
110 {
111 a=find(num[j].x);
112 b=find(num[j].x+W)-1;
113 updata(1,a,b,-num[j].c);
114 j++;
115 }
116 a=find(num[i].x);
117 b=find(num[i].x+W)-1;
118 updata(1,a,b,num[i].c);
119 if(tree[1].max_val>ans)
120 ans=tree[1].max_val;
121 }
122 printf("%I64d\n",ans);
123 }
124 return 0;
125 }

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

總結(jié)

以上是生活随笔為你收集整理的线段树专辑 —— pku 2482 Stars in Your Window的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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