a164. 區間最大連續和＠Morris' Blog｜PChome Online 個人新聞台

2011-06-28 16:35:00| 人氣5,146| 回應0 | 上一篇 | 下一篇

a164. 區間最大連續和

推薦 0 收藏 0 轉貼0 訂閱站台

a164. 區間最大連續和

內容：

給定一個整數序列A_i, 其中1<=i<=N。

有Q筆詢問，每次詢問一個正整數數對L, R，問閉區間 [A_L, A_R]的最大連續和。

什麼叫最大連續和呢？請參見d784: 連續元素的和

也就是說要找到兩個正整數i, j滿足L <=i <=j <= R，且極大化A_i + A_i+1 + ... + A_j的值。

當i, j有多組解時輸出i最小的、再有多組解輸出j最小的。

輸入說明：

輸入含多組測試資料，請用EOF判斷結束。

每組資料：

第一行有兩個正整數N, Q 。

再來一行有以空白分隔的N個整數，依序表示A₁到A_N。

再來會有Q行，每行兩個正整數L, R表示一個詢問。

保證：

單一檔案不超過十筆數據。

1 <= N <= 200,000

1 <= Q <= 100,000

1 <= L <= R <= N

輸入所有數字都是整數且絕對值小於1,000,000,000

輸出說明：

每組測資的輸出第一行請輸出"Case x:"表示為第x組測資，從1開始編號。

接下來輸出Q行，每行輸出三個數字依序表示該筆詢問的i, j以及A_i + A_i+1 + ... + A_j的值。

範例輸入：

10 3
0 0 0 1 0 0 0 -8 -3 5
1 7
8 9
8 10

範例輸出：

Case 1:
1 4 1
9 9 -3
10 10 5

提示：

背景知識：經典應用

第一個檔案就是範例。

第二個檔案共有十組，N=Q=100。

第三個檔案共有兩組，皆為極限測資。

出處：

Asia - Nanjing - 2007/2008 (管理：poao899)

作法 : 線段樹
參考 : http://www.cppblog.com/MatoNo1/archive/2011/04/24/144901.html
線段樹的區間是[i,j]，節點編號k，左右子樹lc, rc，我們將儲存
1. 由左至右 : 從i 開始，但小於 j 的最大連續和 (lmax)
2. 由右至左 : 從j 開始，但大於 i 的最大連續和 (rmax)
3. 中間 : 此區間存在的最大連續和 (midmax)
4. 區間總和 (sum)
得到
1. k.lmax = max(lc.lmax, lc.sum + rc.lmax);
2. k.rmax = max(rc.rmax, rc.sum + lc.rmax);
3. k.midmax = max(lc.midmax, rc.midmax, lc.rmax + rc.lmax);
4. k.sum = lc.sum + rc.sum;

接下來，當我們調查[i,j] 時，會拆成很多個不相交的區間
[i, i1] [i2, i3] [i4..] ...
目前不連續到下一個區間的最大連續和 f0 = max(k.midmax, f1 + k.lmax);/*區間中斷 or 連續+斷*/
目前可連續到下一個區間的最大連續和 f1 = max(k.rmax, f1 + k.sum);/*新的連續 or 連續+連續*/

這個時候，就以我們平常所做的最大連續和"類似"了 (不代表相同)
這裡只是約略講一下，詳情請看參考網址

為了輸出最大連續和的 "最小"區間，搞得我人仰馬翻啦

雖然幾乎是照著打了，我仍學到很多，感謝分享的神犇

/**********************************************************************************/
/* Problem: a164 "區間最大連續和" from Asia - Nanjing - 2007/2008         */
/* Language: C                                                                   */
/* Result: AC (272ms, 13790KB) on ZeroJudge                                      */
/* Author: morris1028 at 2011-06-28 12:40:03                                     */
/**********************************************************************************/

#include<stdio.h>
#define N 262144
#define Maxv 2147483647
long long A[N], Ans, f0, f1;
int B[N], st, ed, st0, ed0, st1, ed1;
struct segment {
    int l, r, m;
    int lc, rc;
    int lst, led, rst, red, mst, med;
    long long sum, lmax, rmax, midmax;
}ST[2*N + 2];
int max(int x, int y) {
    return x >= y ? x : y;
}
void init(int l, int r, int k) {
    ST[k].l = l, ST[k].r = r, ST[k].m = (l + r)>>1;
    if(l == r) {
        ST[k].sum = ST[k].lmax = ST[k].rmax = ST[k].midmax = A[l];
        ST[k].lst = ST[k].led = ST[k].rst = ST[k].red = ST[k].mst = ST[k].med = l;
        return ;
    }
    ST[k].lc = k<<1, ST[k].rc = (k<<1)+1;
    init(l, ST[k].m, ST[k].lc), init(ST[k].m+1, r, ST[k].rc);
    ST[k].sum = ST[ST[k].lc].sum + ST[ST[k].rc].sum;

    ST[k].lmax = max(ST[ST[k].lc].lmax, ST[ST[k].lc].sum + ST[ST[k].rc].lmax);
    ST[k].lst = Maxv, ST[k].led = Maxv;;
    if(ST[ST[k].lc].lmax == ST[k].lmax)
        ST[k].lst = ST[ST[k].lc].lst, ST[k].led = ST[ST[k].lc].led;
    if(ST[ST[k].lc].sum + ST[ST[k].rc].lmax == ST[k].lmax && (ST[k].lst > ST[ST[k].lc].l || (ST[k].lst == ST[ST[k].lc].l && ST[k].led > ST[ST[k].rc].led)))
        ST[k].lst = ST[ST[k].lc].l, ST[k].led = ST[ST[k].rc].led;

    ST[k].rmax = max(ST[ST[k].rc].rmax, ST[ST[k].rc].sum + ST[ST[k].lc].rmax);
    ST[k].rst = Maxv, ST[k].red = Maxv;
    if(ST[ST[k].rc].rmax == ST[k].rmax)
        ST[k].rst = ST[ST[k].rc].rst, ST[k].red = ST[ST[k].rc].red;
    if(ST[ST[k].rc].sum + ST[ST[k].lc].rmax == ST[k].rmax && (ST[k].rst > ST[ST[k].lc].rst || (ST[k].rst == ST[ST[k].lc].rst && ST[k].red > ST[ST[k].rc].r)))
        ST[k].rst = ST[ST[k].lc].rst, ST[k].red = ST[ST[k].rc].r;
    ST[k].midmax = max(max(ST[ST[k].lc].midmax, ST[ST[k].rc].midmax), ST[ST[k].lc].rmax + ST[ST[k].rc].lmax);

    ST[k].mst = Maxv, ST[k].med = Maxv;
    if(ST[ST[k].lc].midmax == ST[k].midmax)
        ST[k].mst = ST[ST[k].lc].mst, ST[k].med = ST[ST[k].lc].med;
    if(ST[ST[k].rc].midmax == ST[k].midmax && (ST[k].mst > ST[ST[k].rc].mst || (ST[k].mst == ST[ST[k].rc].mst && ST[k].med > ST[ST[k].rc].med)))
        ST[k].mst = ST[ST[k].rc].mst, ST[k].med = ST[ST[k].rc].med;
    if(ST[ST[k].lc].rmax + ST[ST[k].rc].lmax == ST[k].midmax && (ST[k].mst > ST[ST[k].lc].rst || (ST[k].mst == ST[ST[k].lc].rst && ST[k].med > ST[ST[k].rc].led)))
        ST[k].mst = ST[ST[k].lc].rst, ST[k].med = ST[ST[k].rc].led;

}
void query(int l, int r, int k) {
    if(ST[k].l > r || ST[k].r < l)
        return ;
    if(ST[k].l >= l && ST[k].r <= r) {
        f0 = max(ST[k].midmax, f1 + ST[k].lmax);
        if(ST[k].midmax == f0 && f1 + ST[k].lmax != f0)
            st0 = ST[k].mst, ed0 = ST[k].med;
        else if(f1 + ST[k].lmax == f0 && ST[k].midmax != f0)
            st0 = st1, ed0 = ST[k].led;
        else {
            if(ST[k].mst < st1 || (ST[k].mst == st1 && ST[k].med < ST[k].led))
                st0 = ST[k].mst, ed0 = ST[k].med;
            else
                st0 = st1, ed0 = ST[k].led;
        }
        int pref1 = f1;
        f1 = max(ST[k].rmax, f1 + ST[k].sum);
        if(ST[k].rmax == f1 && pref1 + ST[k].sum != f1)
            st1 = ST[k].rst, ed1 = ST[k].red;
        else if(pref1 + ST[k].sum == f1 && ST[k].rmax != f1)
            st1 = st1, ed1 = ST[k].r;
        else {
            if(ST[k].rst < st1 || (ST[k].rst == st1 && ST[k].red < ST[k].r))
                st1 = ST[k].rst, ed1 = ST[k].red;
            else
                st1 = st1, ed1 = ST[k].r;
        }

        if(f0 > Ans || (f0 == Ans && st > st0 || (st == st0 && ed > ed0))) Ans = f0, st = st0, ed = ed0;
        if(f1 > Ans || (f1 == Ans && st > st1 || (st == st1 && ed > ed1))) Ans = f1, st = st1, ed = ed1;
        return ;
    }
    query(l, r, ST[k].lc), query(l, r, ST[k].rc);
}
int Input() {
    char cha;
    unsigned int x = 0;
    while(cha = getchar())
        if(cha != ' ' && cha != '\n' || cha == EOF) break;
    if(cha == EOF) return -1;
    x = cha-48;
    while(cha = getchar()) {
        if(cha == ' ' || cha == '\n') break;
        x = x*10 + cha-48;
    }
    return x;
}
main() {
    int n, Q, a, C = 0;
    int i, j;
    while(scanf("%d %d", &n, &Q) == 2) {
        for(a = 1; a <= n; a++)
            scanf("%lld", &A[a]);
        init(1, n, 1);
        printf("Case %d:\n", ++C);
        while(Q--) {
            i = Input(), j = Input();
            f0 = f1 = 0, Ans = -2147483647, st0 = st1 = ed0 = ed1 = i;
            query(i, j, 1);
            printf("%d %d %lld\n", st, ed, Ans);
        }
    }
    return 0;
}

我要檢舉

#a164#區間最大連續和

台長： Morris

您可能對以下文章有興趣

[ZJ][BIT+DP] a596. 祖靈要段考了!!!!!!!!

[ZJ][LCA][offline] d767. 血緣關係

a129. 最小生成樹

[ZJ][heap] a605. 交錯和

人氣(5,146) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: ZeroJudge |
此分類下一篇:d799. 区间求和 (樹狀數組版本)
此分類上一篇:d017. AB Circle

回應(0)