UVa 1400 - Ray, Pass me the dishes!

#数据结构 #线段树

Published on 2016-01-05

描述

给出一个长度为 $n(n\le500000)$ 的整数序列 $D$ ，你的任务是对 $m(m\le500000)$ 个询问做出回答。对于询问 $(a,b)$ ，需要找到两个下标 $x$ 和 $y$ ，使得 $a\le x\le y\le b$ ，并且 $D_{x}+D_{x+1}+....+D_{y}$ 尽量大。如果有多组满足条件的 $x$ 和 $y$ ，让 $x$ 尽量小，如果还有多个解， $y$ 也应该尽量小。

样例输入

3 1
1 2 3
1 1

样例输出

Case 1:
1 1

分析

对于单个查询，我们是可以在 $O(n)$ 的时间复杂度内得出答案的，扫一遍记录一下就 OK，但这对于大量的查询显然不够，我们必须优化。
看到区间以及频繁的查询，于是想到区间类的数据结构 - 树状数组或线段树。但是这题有些特殊，它是求一段区间内连续最大和，所以并不能简单的合并两个子区间里面的结果，因此这不是 RMQ(Range Maximum Query) 类型，我们试着用更强大的线段树＋分治思想搞定它。
对于线段树的每一个节点，若其代表区间为 $[l, r)$ ，维护四个信息：首先是 $\mathrm{sum}$ ，即区间内元素和，这个没什么说的，属于基本操作之一。 $\mathrm{maxPrefix}$ 表示区间 $[l, r)$ 内最大的前缀和，即 $\mathrm{maxPrefix} = \max\{\sum\limits_{i = l}^{t}D_{i}, t \in [l, r)\}$ 。 $\mathrm{maxSuffix}$ 表示区间 $[l, r)$ 内最大的后缀和，即 $\mathrm{maxSuffix} = \max\{\sum\limits_{i = t}^{r - 1}D_{i}, t \in [l, r)\}$ 。最后一个信息 $\mathrm{maxSub}$ 则表示区间 $[l, r)$ 内的连续最大和。
如何计算，显然不能鲁莽的合并区间，那样会有不连续的问题。对于节点 $K$ ，代表区间为 $[l, r)$ ，它的左右儿子为 $i, j$ ，那么他的最大前缀和只有可能是两种情况，一种是跨过区间中点，一种是不跨过区间中点，即

\mathrm{maxPrefix}_{K} = \max \begin{cases} \mathrm{maxPrefix}_{i}\\ \mathrm{sum}_{i} + \mathrm{maxPrefix}_{j} \end {cases}

同理，给出 $\mathrm{maxSuffix}$ 的计算公式:

\mathrm{maxSuffix}_{K} = \max \begin{cases} \mathrm{maxSuffix}_{j}\\ \mathrm{sum}_{j} + \mathrm{maxSuffix}_{i} \end {cases}

那么 $\mathrm{maxSub}$ 也不难搞定：

\mathrm{maxSub}_{K} = \max \begin{cases} \mathrm{maxSub}_{i} \\\mathrm{maxSub}_{j} \\\mathrm{maxSuffix}_{j} + \mathrm{maxPrefix}_{i}\end{cases}

放出图帮助理解：

接下来唯一麻烦的地方在于搞出区间，可以通过写辅助函数和打包返回值搞定，参见代码。

代码

//  Created by Sengxian on 1/5/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 1513 线段树
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <deque>
#include <limits>
#include <set>
using namespace std;
const int maxn = 500000 + 3;
typedef long long Type;
inline Type max(Type a, Type b, Type c) {
    return max(max(a, b), c);
}
struct Segment {
    Type x, y;
    Segment(Type x = 0, Type y = 0): x(x), y(y) {}
    bool operator < (const Segment &s) const {
        if(x != s.x) return x < s.x;
        else return y < s.y;
    }
    Segment unite(const Segment &s) const {
        return Segment(min(x, s.x), max(y, s.y));
    }
    void printLine() {
        printf("%lld %lld\n", x, y);
    }
};

struct ret {
    Type val; Segment s;
    ret(Type val, Segment s): val(val), s(s) {}
};

struct SegmentTree {
    static const Type maxNode = (1 << 19) * 2 + 100;
    static const Type INF = 1LL << 60;
    Type sum[maxNode], maxSub[maxNode], maxPrefix[maxNode], maxSuffix[maxNode], n;
    Segment maxSubSeg[maxNode], maxPrefixSeg[maxNode], maxSuffixSeg[maxNode];
    Segment deal(Type v1, Type v2, const Segment &s1, const Segment &s2) {
        if(v1 != v2) {
            if(v1 > v2) return s1;
            else return s2;
        }else if(s1 < s2) return s1;
        else return s2;
    }
    Segment deal(Type v1, Type v2, Type v3, const Segment &s1, const Segment &s2, const Segment &s3) {
        return deal(max(v1, v2), v3, deal(v1, v2, s1, s2), s3);
    }
    void init(int _n, Type *a) {
        int bits = 0;
        n = 1;
        while(n < _n) n *= 2, bits++;
        for(int i = n - 1; i < n * 2 - 1; ++i) {
            sum[i] = maxPrefix[i] = maxSuffix[i] = maxSub[i] = i - (n - 1) < _n ? a[i - (n - 1)] : 0;
            maxPrefixSeg[i] = maxSuffixSeg[i] = maxSubSeg[i] = Segment(i - (n - 1), i - (n - 1) + 1);
        }
        for(int i = bits - 1; i >= 0; --i) {
            int start = (1 << i) - 1;
            int len = 1 << (bits - i);
            for(Type j = start; j < start + (1 << i); ++j) {
                int l = (j - start) * len;
                int r = l + len;
                sum[j] = sum[j * 2 + 1] + sum[j * 2 + 2];
                maxPrefix[j] = max(maxPrefix[j * 2 + 1], sum[j * 2 + 1] + maxPrefix[j * 2 + 2]);
                maxPrefixSeg[j] = deal(maxPrefix[j * 2 + 1], sum[j * 2 + 1] + maxPrefix[j * 2 + 2], maxPrefixSeg[j * 2 + 1], maxPrefixSeg[j * 2 + 2].unite(Segment(l, (l + r) / 2)));
                maxSuffix[j] = max(maxSuffix[j * 2 + 2], sum[j * 2 + 2] + maxSuffix[j * 2 + 1]);
                maxSuffixSeg[j] = deal(maxSuffix[j * 2 + 2], sum[j * 2 + 2] + maxSuffix[j * 2 + 1], maxSuffixSeg[j * 2 + 2], maxSuffixSeg[j * 2 + 1].unite(Segment((l + r) / 2, r)));
                maxSub[j] = max(maxSub[j * 2 + 1], maxSub[j * 2 + 2], maxSuffix[j * 2 + 1] + maxPrefix[j * 2 + 2]);
                maxSubSeg[j] = deal(maxSub[j * 2 + 1], maxSub[j * 2 + 2], maxSuffix[j * 2 + 1] + maxPrefix[j * 2 + 2],
                    maxSubSeg[j * 2 + 1], maxSubSeg[j * 2 + 2], maxSuffixSeg[j * 2 + 1].unite(maxPrefixSeg[j * 2 + 2]));
            }
        }
    }
    Type querySum(Type a, Type b, Type l, Type r, Type k) {
        if(b <= l || a >= r) return 0;
        else if(l >= a && r <= b) return sum[k];
        return querySum(a, b, l, (l + r) / 2, k * 2 + 1) + querySum(a, b, (l + r) / 2, r, k * 2 + 2);
    }
    ret queryPrefix(Type a, Type b, Type l, Type r, Type k) {
        if(b <= l || a >= r) return ret(-INF, Segment());
        else if(l >= a && r <= b) return ret(maxPrefix[k], maxPrefixSeg[k]);
        ret r1 = queryPrefix(a, b, l, (l + r) / 2, k * 2 + 1);
        ret r2 = queryPrefix(a, b, (l + r) / 2, r, k * 2 + 2);
        ret r3 = ret(r2.val + querySum(a, b, l, (l + r) / 2, k * 2 + 1), r2.s.unite(Segment(l, (l + r) / 2)));
        return ret(max(r1.val, r3.val), deal(r1.val, r3.val, r1.s, r3.s));
    }
    ret querySuffix(Type a, Type b, Type l, Type r, Type k) {
        if(b <= l || a >= r) return ret(-INF, Segment());
        else if(l >= a && r <= b) return ret(maxSuffix[k], maxSuffixSeg[k]);
        ret r1 = querySuffix(a, b, (l + r) / 2, r, k * 2 + 2);
        ret r2 = querySuffix(a, b, l, (l + r) / 2, k * 2 + 1);
        ret r3 = ret(r2.val + querySum(a, b, (l + r) / 2, r, k * 2 + 2), r2.s.unite(Segment((l + r) / 2, r)));
        return ret(max(r1.val, r3.val), deal(r1.val, r3.val, r1.s, r3.s));
    }
    ret querySub(Type a, Type b, Type l, Type r, Type k) {
        if(b <= l || a >= r) return ret(-INF, Segment());
        else if(l >= a && r <= b) return ret(maxSub[k], maxSubSeg[k]);
        ret r1 = querySub(a, b, l, (l + r) / 2, k * 2 + 1);
        ret r2 = querySub(a, b, (l + r) / 2, r, k * 2 + 2);
        ret r3 = querySuffix(a, b, l, (l + r) / 2, k * 2 + 1);
        ret r4 = queryPrefix(a, b, (l + r) / 2, r, k * 2 + 2);
        ret r5 = ret(r3.val + r4.val, r3.s.unite(r4.s));
        return ret(max(r1.val, r2.val, r5.val), deal(r1.val, r2.val, r5.val, r1.s, r2.s, r5.s));
    }
    //[a, b)
    inline ret Query(Type a, Type b) {
        return querySub(a, b, 0, n, 0);
    }
}Solver;

inline Type ReadInt() {
    Type n = 0; char ch = getchar(); bool flag = false;
    while(ch < '0' || ch > '9') {
        if(ch == '-') flag = true;
        ch = getchar();
    }
    do {
        n = n * 10 + ch - '0';
        ch = getchar();
    }while(ch >= '0' && ch <= '9');
    return flag ? -n : n;
}

int n, m;
Type a[maxn];

int main() {
    int caseNum = 0;
    while(~scanf("%d%d", &n, &m)) {
        printf("Case %d:\n", ++caseNum);
        for(int i = 0; i < n; ++i) a[i] = ReadInt();
        Solver.init(n, a);
        for(int i = 0; i < m; ++i) {
            int x = ReadInt() - 1, y = ReadInt();
            ret r = Solver.Query(x, y);
            Segment s = r.s;
            s.x++;
            s.printLine();
        }
    }
    return 0;
}

附加输入

499 499
282475249 984943658 -470211272 -457850878 7237709 -115438165 -74243042 137522503 16531729 -143542612 474833169 998097157 -131570933 404280278 -505795335 636807826 -101929267 -704877633 624379149 784558821 110010672 617819336 156091745 -899894091 -937186357 25921153 -590357944 -357571490 -927702196 -130060903 -83454666 685118024 60806853 194847408 -158374933 -824938981 962408013 997389814 107554536 654001669 269220094 478446501 351934195 557810404 908194298 -657821123 102246882 -816731566 -807130337 -892053144 4844897 382955828 227619358 70982397 -70477904 606946231 912844175 808266298 -456880399 -280090412 -589673557 -889688008 524325968 515204530 -681910962 -400285365 -463179852 832633821 316824712 815859901 -51724831 -318153057 -877819790 -213110679 49077006 -63936098 428975319 -351345223 398556760 724586126 23129506 436476770 -936329094 -304987844 -881140534 -901915394 348318738 -784559590 -290145159 977764947 971307217 -755539 462242385 -951894885 848682420 -86531968 755699915 992663534 -358796011 771024152 -507977295 -49590396 -621301815 104740033 889119397 882410547 567121210 -536830211 -517273377 41000625 127401868 140002776 49997439 -464689331 -968456301 -911300560 -298918984 124639789 957828015 105222769 -944303455 732267506 454233502 -329863108 323602331 -1887638 -561939997 897054849 461495731 796198014 779636775 175530180 351995223 -458588260 834991545 34837525 -578134256 -609960597 -683337704 -605925150 -24301412 -111482797 -760348381 -855007065 -379847699 338725129 552265483 218264607 363045322 706755176 616927224 -360280366 -284660444 -684570285 -252193898 129841133 262696576 -509658266 347221711 -847320614 195795737 678620591 -135048762 262976197 925238588 795054873 959637304 -832861200 -168068960 545293947 -452207730 564674546 28841238 -18984926 988774857 420250114 300601360 -322968418 738342585 122721015 32106102 380786643 971062967 83245269 812423303 978719103 -47424385 -518163459 -937673930 -614285132 493959603 618907920 -9135231 -171620203 -939824520 603481258 13618676 -113423934 -168279879 -463482574 346174542 523252771 -601915879 798669970 -666082723 -222902971 666190318 -118710299 -344185621 -637850124 -26076958 -116666771 -322791560 -790318751 -240764503 711192801 119315080 -3559274 63040413 -51519025 -586901783 -151624117 -263081550 -404319195 318824511 -270438666 -48760593 799809565 -556228742 911254352 928256141 -633413200 970343127 429157787 -450031625 174619517 -377901842 927515974 476211373 -795739911 90245054 172556929 652354189 -537204356 -651659860 -609005592 -463866116 -78098867 -476026939 -401494901 797716616 501848671 -356326671 343077045 -421620240 -38299453 333685350 38535563 -550207533 115307827 114919531 -140351516 -98478515 -706642601 596168661 368034324 -18044936 547517015 -265963216 343775973 225882720 791481169 702715827 -238616728 628320384 502789949 -8416046 -777568666 977260520 -516341991 -905333258 622268744 -464685718 -132666825 854658689 -528073014 822102918 -987333029 -708006727 -6933754 -427408396 401203083 -287846865 31615252 -301377876 746232675 94482710 791728192 -707454747 356701299 88949715 647259579 115195164 473553501 191110289 -517114033 -562165089 -812535217 -499521038 8240338 -98603321 73536496 67943788 270425987 707765235 -152185684 866683784 -76422667 862972615 318665976 373365825 1271631 751072698 -230092639 -29909503 333748765 737904107 -207314365 48114454 -840127450 448530832 -499932141 -412281977 742753900 302173465 476003622 258459317 -56564048 -637121029 166052708 987502657 924375752 -785108621 292006996 115266930 -346645555 233429312 141231427 -432477444 178402198 -434444856 -227464303 947712914 78626766 67981921 121122752 -75289719 -230168410 185044669 312349943 657922431 -45139816 496786971 45501370 -525679891 594094833 -601518177 -139217683 -505523489 283070434 976226904 -763464891 -494500522 -931706890 -399116813 9907127 844185784 45329870 264032581 508545802 -231367332 -214459759 739972377 -626979010 710298150 230900941 -434826720 92396112 56219956 -728536152 -342695014 -320514918 -817350101 910819821 398644501 129154961 927703510 -935350805 366782137 67439096 121447421 595278518 -260276489 -743532054 18358643 245245250 891469415 -407052494 543867758 -156485092 -887766714 -192958060 -895063368 448891847 -746004787 652188234 -925270571 -44687875 810641871 476562293 164973471 -25725764 511142630 -95688080 462863342 -778248382 -705698828 157863575 -39109000 -73005947 -3266087 313952733 -172490261 -876554400 -68370778 425373423 -421567014 236261662 257726610 790709218 -288775055 319518555 137606534 864877321 759921226 803694459 30316714 388337879 -715914100 768094285 -717918284 -311164915 -432063067 -675810707 -293320728 -977466363 109242890 567222278 790245761 -362834840 -983646000 -334734507 -430166551 -706993431 -619880739 -688507584 -544374108 -497991454 801783028 158592370 215867947 -907424543 -629306008 767780552 -265768163 994411019 28195356 108408487 279743899 -855794244 -224582466 789665274 -414318909 40621834 418069684 123289549 -545747467 -797619589 417097773 380889295 -148637874 694558231 -949983028 -594139070 251766297 796102646 -714958111 -150957463 -996923781
499 499
261 499
331 498
24 499
190 498
57 499
190 499
448 498
365 498
114 499
57 498
40 499
262 499
63 498
326 499
330 499
474 498
9 498
442 499
51 499
152 499
205 499
116 499
257 498
5 498
17 498
313 498
492 499
382 499
100 498
142 499
452 499
361 498
312 499
334 498
261 498
221 498
355 499
191 499
169 499
214 499
475 498
93 499
44 498
44 499
197 499
120 499
128 499
318 498
303 499
352 499
336 498
192 499
205 499
263 498
450 499
123 499
107 499
292 499
452 499
202 499
176 498
269 498
383 498
473 498
87 498
245 498
482 498
286 498
318 499
289 499
79 498
418 499
358 498
43 499
276 499
202 499
23 499
283 499
283 498
480 498
322 498
439 499
434 499
453 499
257 499
448 498
386 498
269 499
110 498
70 499
185 498
495 498
370 499
256 499
224 499
61 498
379 498
148 499
102 498
135 499
307 498
400 499
347 499
204 498
147 498
460 499
470 499
171 499
448 498
286 498
163 498
84 498
426 498
188 499
434 498
326 498
355 499
221 498
206 499
114 498
269 498
491 498
272 499
132 499
438 499
461 499
18 498
213 498
461 499
232 498
426 499
110 498
289 499
280 498
376 498
444 499
407 498
428 498
480 499
232 498
258 499
257 498
221 499
395 499
216 499
170 498
134 499
493 499
73 498
75 498
293 498
380 498
404 498
56 499
485 499
17 498
203 499
284 499
148 499
364 498
219 498
76 498
346 498
228 499
246 498
321 499
95 499
276 499
68 499
233 499
228 499
240 498
98 499
235 498
391 499
435 498
323 499
365 499
462 498
144 498
276 498
182 499
96 499
477 499
141 498
3 499
436 498
99 499
368 499
300 498
127 498
188 498
358 498
238 499
87 499
344 499
129 498
91 499
219 499
312 498
371 499
97 499
51 499
496 498
322 499
155 498
327 498
374 498
332 498
102 499
443 499
363 498
101 499
95 499
450 498
416 499
69 499
373 498
29 498
471 499
70 498
317 499
13 499
147 498
187 499
288 498
485 498
494 499
215 499
20 499
92 498
375 499
379 499
142 498
234 499
382 499
421 499
48 499
472 498
302 498
136 499
93 498
403 498
118 498
404 499
360 498
351 498
287 498
430 498
3 499
19 499
424 498
400 498
334 499
154 499
404 499
57 499
98 498
374 499
200 499
323 498
302 499
77 498
394 499
61 499
59 498
248 498
49 499
45 498
228 499
169 498
413 499
313 498
126 498
326 499
65 499
172 499
292 499
67 498
116 499
32 499
264 498
58 498
276 498
59 498
484 499
232 498
246 499
41 499
136 498
486 499
267 499
371 499
129 498
196 498
149 498
476 499
63 498
7 499
473 498
112 498
438 498
209 499
213 499
85 499
25 498
188 499
190 499
146 499
482 498
208 499
264 499
132 498
203 499
66 498
344 499
387 498
194 498
201 499
376 498
4 499
448 498
315 499
14 498
167 499
261 499
113 498
448 498
345 499
105 499
352 499
168 498
253 498
331 499
432 499
243 498
74 499
203 498
185 498
441 498
305 499
298 498
326 498
171 498
36 498
329 499
19 498
403 499
203 498
424 499
358 498
254 498
361 498
30 498
410 499
51 499
35 498
100 498
392 498
231 499
99 499
124 498
54 498
466 498
352 498
139 498
469 499
313 498
460 499
38 498
27 499
30 498
274 498
365 498
474 499
436 498
470 499
11 498
278 498
58 499
309 499
146 498
461 498
480 499
360 498
138 499
459 498
341 498
259 498
443 499
105 498
187 499
443 498
23 498
123 499
448 498
12 498
135 499
345 499
200 499
86 499
158 498
206 499
459 498
288 499
471 499
418 499
77 499
435 499
369 498
22 498
165 498
417 498
69 498
197 499
10 498
336 498
340 499
403 499
163 498
48 498
480 499
396 499
341 499
268 498
197 498
393 498
368 498
403 499
326 498
220 499
447 499
411 498
250 498
150 498
250 499
251 498
221 499
159 499
25 499
393 498
309 498
273 498
326 499
152 498
124 498
147 499
492 499
125 499
27 499
308 498
78 498
304 499
443 498
428 498
275 499
228 498
451 498
100 498
179 499
112 498
49 499
53 498
367 499
493 498
181 498
197 499
120 499
338 499
473 498
452 498
406 498
337 498
362 498
404 498
104 499
195 498
422 498
388 498
362 498
229 499
194 498
127 499
386 499
262 498
429 499
148 498
336 499
433 498
70 498
171 498
211 499
232 499
72 499
104 498
205 498
80 499
406 499

附加输出

UVa 11992 - Fast Matrix Operations(线段树模板) UVa 246 - 10-20-30

Sengxian's Blog