(Zerojudge) b332: NOIP2013 3.小朋友的数字

https://zerojudge.tw/ShowProblem?problemid=b332

有點小小的陷阱QQ

當初我想說，寫一個線段樹求區間連續最大和，開long long，結果一直WA最後兩筆。

仔細想想，最後有可能爆long long!!!!  QQ (想想全部都是10^9的case !!!)

附上悲慘的code：

#include <iostream>
#include <stdio.h>
using namespace std;

typedef __int128 LL;
const int MAX_N = 1e6 + 6;
const LL INF = 1e17 + 6;

struct Meruru {
    LL sum;
    LL lmax,rmax,midmax;
    void shootingstars(LL _val) {
        sum=lmax=rmax=midmax=_val;
    }
};

Meruru empty={0,-INF,-INF,-INF};

bool operator==(const Meruru &m1,const Meruru &m2) {
    return m1.lmax==m2.lmax && m1.rmax==m2.rmax && m1.midmax==m2.midmax && m1.sum == m2.sum;
}

Meruru pull(Meruru m1,Meruru m2) {
    Meruru meruru;
    if (m1 == empty) return m2;
    if (m2 == empty) return m1;
    meruru.sum = m1.sum+m2.sum;
    meruru.lmax = max(m1.lmax,m1.sum+m2.lmax);
    meruru.rmax = max(m2.rmax,m2.sum+m1.rmax);
    meruru.midmax = max(max(m1.midmax,m2.midmax),m1.rmax+m2.lmax);
    return meruru;
}

struct Node {
    Node *lc,*rc;
    Meruru meruru;
    Node() {
        lc=rc=NULL;
        meruru = empty;
    }
};

LL a[MAX_N];

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

Meruru query(Node* node,int L,int R,int l,int r) {
    if (l>R || L>r) return empty;
    else if (l<=L && R<=r) return node->meruru;
    int mid=(L+R)>>1;
    return pull(query(node->lc,L,mid,l,r),query(node->rc,mid+1,R,l,r));
}

LL p[MAX_N];
LL pp[MAX_N];

int main () {
    int n,mod;
    scanf("%d %d",&n,&mod);
    for (int i=1;n>=i;i++) {
        long long x;
        scanf("%lld",&x);
        a[i]=x;
//        scanf("%lld",&a[i]);
    }
    Node* root=Build(1,n);
    for (int i=1;n>=i;i++) {
        Meruru meruru=query(root,1,n,1,i);
        p[i] = meruru.midmax;
    }
    pp[1] = p[1];
    LL mx=pp[1]+p[1];
    for (int i=2;n>=i;i++) {
        pp[i] = mx;
        mx = max(mx,pp[i] + p[i]);
    }
    mx = pp[1];
    for (int i=1;n>=i;i++) {
        mx = max(mx,pp[i]);
    }
    if (mx<0) {
        printf("%d\n",int(LL(mx)%mod));
    }
    else printf("%d\n",int(mx%mod));
}