系统是 Linux,软件是 VScode,PROBLEMS 里面无误,用了编译指令后 CE。
#include<bits/stdc++.h>
#define int long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int N=2e5+5;
int n,sum,y[N],res[N],s[N],L,ans;
struct node{
int val,l,r;
node operator +(const node &o) const{ return node({val+o.val,l,o.r}); }
friend bool operator <(node a,node b){ return a.val<b.val||(a.val&&a.l<b.l); }
};
struct ST{
node lmax[2],rmax[2],ans[2],sum[2];
bool tag;
friend ST operator +(ST a,ST b){
ST ans;
ans.ans[0]=max({a.ans[0],b.ans[0],a.rmax[0]+b.lmax[0]});
ans.lmax[0]=max(a.lmax[0],a.sum[0],b.lmax[0]);
ans.rmax[0]=max(b.rmax[0],b.sum[0]+a.rmax[0]);
ans.sum[0]=a.sum[0]+b.sum[0];
ans.ans[1]=max({a.ans[1],b.ans[1],a.rmax[1]+b.lmax[1]});
ans.lmax[1]=max(a.lmax[1],a.sum[1],b.lmax[1]);
ans.rmax[1]=max(b.rmax[1],b.sum[1]+a.rmax[1]);
ans.sum[1]=a.sum[1]+b.sum[1];
return ans;
}
}t[N<<2];
void update(int p){
t[p].tag^=1;
swap(t[p].ans[0],t[p].ans[1]);
swap(t[p].lmax[0],t[p].lmax[1]);
swap(t[p].rmax[0],t[p].rmax[1]);
swap(t[p].sum[0],t[p].sum[1]);
}
void pushdown(int p){
if(t[p].tag){
update(ls),update(rs);
t[p].tag=0;
}
}
void build(int p,int l,int r){
if(l==r){
t[p].lmax[0]=t[p].rmax[0]=t[p].sum[0]=t[p].ans[0]=node({y[l],l,l});
t[p].lmax[1]=t[p].rmax[1]=t[p].sum[1]=t[p].ans[1]=node({-y[l],l,l});
return;
}
int mid=l+r>>1;
build(ls,l,mid),build(rs,mid+1,r);
t[p]=t[ls]+t[rs];
}
void update(int p,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
update(p);
return;
}
pushdown(p);
int mid=l+r>>1;
if(ql<=mid) update(ls,l,mid,ql,qr);
if(mid<qr) update(rs,mid+1,r,ql,qr);
t[p]=t[ls]+t[rs];
}
signed main(){
// freopen("hollow.in","r",stdin);
// freopen("hollow.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n,L=n+1;
for(int i=1,x;i<=n;++i){
cin>>x>>y[i];
if(x) sum+=y[i],y[i]=-y[i];
res[i]=max(res[i-1],s[i]=s[i-1]+y[i]);
}
build(1,1,n);
for(int i=0;i<=n;++i){
cout<<res[L-1]+ans<<endl;
ST res=t[1];
if(res.ans[0].val>0){
L=min(L,res.ans[0].l);
ans+=res.ans[0].val;
update(1,1,n,res.ans[0].l,res.ans[0].r);
}
}
return 0;
}