有點小小的陷阱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)); }
