最后，答案使用 __int128 存储，我赛时用 long long ，100->56。
代码：
#include
using namespace std;
char ibuf[1<<23],obuf[1<<23];
char *ilptr=ibuf,*irptr=ibuf,*optr=obuf;
#define getch() (__builtin_expect(ilptr==irptr,false)?(ilptr=ibuf,irptr=ibuf+fread(ibuf,1,1<<22,stdin),(__builtin_expect(ilptr==irptr,false)?EOF:*ilptr++)):*ilptr++)
#define flh() (fwrite(obuf,1,optr-obuf,stdout),optr=obuf,0)
#define putch(c) (*optr=(c),++optr,(__builtin_expect(optr-obuf>=(1<<22),false)?flh():0))
unsigned int rdu32(){char c = getch();while(c<'0'||c>'9') c = getch();unsigned int ans = 0;while(c>='0'&&c<='9') ans = (ans<<3)+(ans<<1)+(c^0x30),c = getch();return ans;
}
int rdi32(){char c = getch();int f = 1;while(c<'0'||c>'9'){if(c=='-') f = -1;c = getch();}int ans = 0;while(c>='0'&&c<='9') ans = (ans<<3)+(ans<<1)+(c^0x30),c = getch();return ans*f;
}
void wtu128(unsigned __int128 a){if(!a){putch('0');return;}char buf[45];int btp = 0;for(;a;a/=10) buf[++btp] = a%10^0x30;for(;btp;btp--) putch(buf[btp]);
}
const __int128 INF = 1e36+5;
const int N = 3e5+5;
int b[N];
__int128 a[N],sum[N],mnsum[N];
namespace seg1{__int128 mn[N<<2],lzy[N<<2];void upd(int rt){mn[rt] = min(mn[rt<<1],mn[rt<<1|1]);}void build(int rt,int l,int r){lzy[rt] = 0;if(l==r){mn[rt] = sum[l];return;}int mid = (l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);upd(rt);}void phd(int rt){mn[rt<<1]+=lzy[rt],lzy[rt<<1]+=lzy[rt],mn[rt<<1|1]+=lzy[rt],lzy[rt<<1|1]+=lzy[rt];lzy[rt] = 0;}void ch(int rt,int t,int nl,int nr,int v){if(nl>=t){mn[rt]+=v,lzy[rt]+=v;return;}phd(rt);int mid = (nl+nr)>>1;if(mid>=t) ch(rt<<1,t,nl,mid,v);ch(rt<<1|1,t,mid+1,nr,v);upd(rt);}__int128 ask(int rt,int l,int r,int nl,int nr){if(nl>=l&&nr<=r) return mn[rt];phd(rt);int mid = (nl+nr)>>1;__int128 ans = INF;if(l<=mid) ans = min(ans,ask(rt<<1,l,r,nl,mid));if(r>mid) ans = min(ans,ask(rt<<1|1,l,r,mid+1,nr));return ans;}int find(int rt,int t,__int128 v,int nl,int nr){if(mn[rt]>=v) return 0;if(nl==nr) return nl;phd(rt);int mid = (nl+nr)>>1;if(t<=mid) return find(rt<<1,t,v,nl,mid);int ans = find(rt<<1|1,t,v,mid+1,nr);if(ans) return ans;return find(rt<<1,t,v,nl,mid);}
}
namespace seg2{__int128 ans[N<<2],mn[N<<2],lzy[N<<2],cnt[N<<2];void upd(int rt){ans[rt] = ans[rt<<1]+ans[rt<<1|1];mn[rt] = min(mn[rt<<1],mn[rt<<1|1]);cnt[rt] = cnt[rt<<1]+cnt[rt<<1|1];}void build(int rt,int l,int r){lzy[rt] = 0;if(l==r){ans[rt] = sum[l]-b[l]-mnsum[l+1];if(ans[rt]<=0) mn[rt] = INF,ans[rt] = 0,cnt[rt] = 0;else mn[rt] = ans[rt],cnt[rt] = 1;return;}int mid = (l+r)>>1;build(rt<<1,l,mid),build(rt<<1|1,mid+1,r);upd(rt);}void phd(int rt){if(mn[rt<<1]!=INF) mn[rt<<1]-=lzy[rt],lzy[rt<<1]+=lzy[rt],ans[rt<<1]-=lzy[rt]*cnt[rt<<1];if(mn[rt<<1|1]!=INF) mn[rt<<1|1]-=lzy[rt],lzy[rt<<1|1]+=lzy[rt],ans[rt<<1|1]-=lzy[rt]*cnt[rt<<1|1];lzy[rt] = 0;}void ch(int rt,int l,int r,int nl,int nr,int v){if(mn[rt]==INF) return;if(l<=nl&&nr<=r&&mn[rt]>v){ans[rt]-=v*cnt[rt];lzy[rt]+=v,mn[rt]-=v;return;}if(nl==nr){ans[rt] = 0,mn[rt] = INF,cnt[rt] = 0;return;}phd(rt);int mid = (nl+nr)>>1;if(l<=mid) ch(rt<<1,l,r,nl,mid,v);if(r>mid) ch(rt<<1|1,l,r,mid+1,nr,v);upd(rt);}
}
int main(){freopen("freight.in","r",stdin);freopen("freight.out","w",stdout);int c = rdu32(),t = rdu32();while(t--){int n = rdu32(),q = rdu32();for(int i=1;i<=n;i++) a[i] = rdi32(),sum[i] = sum[i-1]+a[i];mnsum[n] = sum[n];for(int i=n-1;i;i--) mnsum[i] = min(mnsum[i+1],sum[i]);for(int i=1;i=1;i=(i==1?0:seg1::find(1,i-1,nmn,1,n))){seg2::ch(1,i,pre,1,n-1,nmn-mn);pre=i-1,nmn = seg1::ask(1,i,i,1,n);if(nmn<=mn) break;}if(nmn>mn&&pre) seg2::ch(1,1,pre,1,n-1,nmn-mn);}else{int k = rdu32();if(k<-seg1::ask(1,1,n,1,n)) putch('-'),putch('1'),putch('\n');else wtu128(seg2::ans[1]),putch('\n');}}}flh();return 0;
}