(Zj) 區間連續最大和

http://zerojudge.tw/ShowProblem?problemid=a164

有夠難寫！！！

因為這題還要維護答案的範圍，要不然基本上，答案範圍的可以不用存XDDD

就是呢，對於每個區間，你都要維護4樣東西："最大前綴和"、"最大後綴和"、"最大區間總和"、"區間總和"，我分別以lmax, rmax, midmax, sum表示

其中，在合併時：
1. lmax = max(lc->lmax, lc->sum + rc->lmax)
2. rmax = max(rc->rmax, lc->rmax + rc->sum)
3. midmax = max( max(lc->midmax, rc->midmax) , lc->rmax + rc->lmax);
4. sum = lc->sum + rc->sum;

想想看為什麼！

然後，在求答案時：

要維護兩種答案f0(不可以連續到下一個區間), f1(可以連續到下一個區間)

維護方法分別是：
f0 = max( node->midmax , pref1 + node->lmax);
f1 = max( node->rmax, pref1+node->sum);

pref1代表上一個f1

因此，在initialize詢問時，要預設f0 = f1 = 0 !!!

太神奇啦！！！

2016.10.19 Update : 其實如果可以用treap做的話，會更直觀一點(切來切去之後，求midmax即為答案，這裡 是指標版)

這樣就AC了

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <math.h>

typedef long long LL;

const int INF = 2000000000;

inline long long  max(int a,int b) {
    return (a<b?b:a);
}

struct Node {
    Node* lc;
    Node* rc;
    int l,r,mid;
    int lst,led;
    int rst,red;
    int mst,med;
    LL lmax,rmax,midmax,sum;
    Node () {
        lc=rc=NULL;
        l=r=mid=lst=led=mst=med=lmax=rmax=midmax=sum=0;
    }
    void init(int pos,int val) {
        l=r=mid=lst=led=rst=red=mst=med=pos;
        lmax=rmax=midmax=sum=val;
    }
    void pull() {
        l=lc->l;
        r=rc->r;
        mid=(l+r)>>1;
        sum=lc->sum+rc->sum;
        lmax = max(lc->lmax, lc->sum + rc->lmax);
        lst=led=mst=med=rst=red=INF;
        if (lmax == lc->lmax) {
            lst=lc->lst;
            led=lc->led;
        }
        //其實後面可以不用，但是因為要輸出範圍XDDD 
        if (lmax == lc->sum + rc->lmax && (lst > lc->lst || lst==lc->lst && led>rc->led)) {
            lst=lc->lst; //can also be = lc->l
            led=rc->led;
        }
        rmax = max(rc->rmax,rc->sum + lc->rmax);
        if (rmax == rc->rmax) {
            rst=rc->rst;
            red=rc->red;
        }
        if (rmax== rc->sum + lc->rmax && (rst > lc->rst || rst==lc->rst && led > rc->red)) {
            red=rc->red; //can also be = rc->r
            rst=lc->rst;
        }
        midmax = max(max(lc->midmax,rc->midmax) , lc->rmax + rc->lmax);
        if (midmax==lc->midmax) {
            mst=lc->mst;
            med=lc->med;
        }
        if (midmax==rc->midmax && (mst>rc->mst || mst==rc->mst && med>rc->med)) {
            mst=rc->mst;
            med=rc->med;
        }
        if (midmax==lc->rmax + rc->lmax && (mst>lc->rst || mst==lc->rst && med>rc->led)) {
            mst=lc->rst;
            med=rc->led;
        }
    }
};

const int MAX_N = 200004;
int v[MAX_N];

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) {
        node->init(L,v[L]);
        return node;
    }
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

LL ans;
int ansst,ansed;
LL f0,f1;
int f0st,f0ed,f1st,f1ed;

void query(Node* node,int L,int R,int l,int r) {
    if (L>r || l>R) return;
    else if (l<=L && R<=r) {
        f0 = max(node->midmax,f1+node->lmax);
        if (f0==node->midmax && f0!=f1+node->lmax) {
            f0st=node->mst;
            f0ed=node->med;
        }
        else if (f0==f1+node->lmax && f0 != node->midmax) {
            f0st=f1st;
            f0ed=node->led;
        }
        else {
            if (node->mst < f1st || node->mst==f1st && node->med < node->led) {
                f0st=node->mst;
                f0ed=node->med;
            }
            else {
                f0st=f1st;
                f0ed=node->led;
            }
        }
        LL pref1=f1;
        f1 = max(node->rmax, pref1 + node->sum);
        if (f1==node->rmax && f1!=pref1+node->sum) {
            f1st=node->rst;
            f1ed=node->red;
        }
        else if (f1==pref1+node->sum && f1!=node->rmax) {
            f1st=f1st;
            f1ed=node->r;
        }
        else {
            if (node->rst < f1st || node->rst==f1st && node->red < node->r) {
                f1st=node->rst;
                f1ed=node->red;
            }
            else {
                f1st=f1st;
                f1ed=node->r;
            }
        }
        
        if (f0>ans || f0==ans && f0st<ansst || f0==ans&&f0st==ansst&&f0ed<ansed) {
            ans=f0;
            ansst=f0st;
            ansed=f0ed;
        }
        if (f1>ans || f1==ans && f1st<ansst || f1==ans&&f1st==ansst&&f1ed<ansed) {
            ans=f1;
            ansst=f1st;
            ansed=f1ed;
        }
        return;
    }
    int mid=(L+R)>>1;
    query(node->lc,L,mid,l,r);
    query(node->rc,mid+1,R,l,r);
}

int main () {
    int n,q,cases=0;
    while (scanf("%d %d",&n,&q) != EOF) {
        printf("Case %d:\n",++cases);
        for (int x=1;n>=x;x++) {
            scanf("%d",&v[x]);
        }
        Node* root = Build(1,n);
        while (q--) {
            int i,j;
            scanf("%d %d",&i,&j);
            ans=-INF;
            ansst=ansed=INF;
            f0 = f1 = 0;
            f0st = f0ed = f1st = f1ed = i;
            query(root,1,n,i,j);
            printf("%d %d %lld\n",ansst,ansed,ans);
        }
    }
}
/*
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 連續+連續
*/