hollow
给你一个由 \(n\) 段若干个 \(0\) 或 \(1\) 组成的序列，每次可以选择一段区间翻转，每次操作后问最长不下降子序列长度。
显然地，我们可以把连续的相同数字看成一个带权的整体。
最长不下降子序列（以下用 LIS 来表示）可以枚举分割点，前面都是 \(0\)，后面都是 \(1\)。
对于分割点 \(x\)，它的价值为前面 \(0\) 的数量加后面 \(1\) 的数量，即 \(cnt_{0,x}+(cnt_{1,n}-cnt_{1,x})\)。因为 \(cnt_{1,n}\) 是固定的，我们只需要求最大的 \(cnt_{0,x}-cnt_{1,x}\)。这相当于把 \(0\) 看成 \(1\)，把 \(1\) 看成 \(-1\)，\(s_x\) 表示前缀和，找出最大的 \(s_x\)。
对于一次翻转 \([l,r]\)，相当于 \(s_{1\sim l-1}\) 和 \(s_{r+1 \sim n}\) 不变，\(s_{x,x\in [l,r]}\) 变成 \(s_{[1,l-1]}+s_{[x+1,r]}\)。因为我们可以翻转任意一个区间，因此求 \(\max s'_x\) 就相当于求至多 \(2\) 个不交的区间（必须包含一个左端点为 \(1\) 的区间，当然这个区间的右端点可以为 \(0\)）和的最大值。而翻转 \(k\) 次就相当于求至多 \(k+1\) 个不交的区间和的最大值。可以 DP 求解。\(dp_{i,j}\) 表示枚举到第 \(i\) 块，已经用了 \(j\) 个区间的最大和，转移分第 \(i\) 块是否选择，如果选择需要枚举第 \(i\) 块和前面的几块成为一个区间，时间复杂度 \(O(n^3)\)。
考虑怎么优化选择 \(k\) 个不交的区间的最大和这件事。显然，每次贪心选取最大的区间肯定是假的。考虑反悔贪心。每次找到和最大的区间，把它加上，然后把它的值全部取反，这样下次再选到它的时候就相当于把它的一部分取消选择了。可以用线段树维护最大子区间，取反操作。时间复杂度是 \(O(n\log n)\) 的。所以就是一开始先选出一个左端点为 \(1\) 的最大区间，然后后面 \(n\) 次每次选一个最大子区间（可以选空区间，即不选），计入答案并对它取反即可。
震惊！有人写了 16 个信息的线段树！荣获倒数第 3 短解和第 2 快解！
#include<bits/stdc++.h>
//#define int ll
//#define LOCAL
#define sf scanf
#define pf printf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define ls u<<1
#define rs u<<1|1
#define mid ((l+r)>>1)
using namespace std;
typedef long long ll;
const int N=2e5+7;
int n;
ll x[N],y[N];
int cnt;
struct pi{
ll val,pos;
void _max(ll sum,pi lx,pi rx){
if(lx.val>=sum+rx.val) val=lx.val,pos=lx.pos;
else val=sum+rx.val,pos=rx.pos;
}
void _min(ll sum,pi lx,pi rx){
if(lx.val<=sum+rx.val) val=lx.val,pos=lx.pos;
else val=sum+rx.val,pos=rx.pos;
}
};
struct pi2{
ll val,pl,pr;
void _max(pi2 lx,pi2 rx,pi lxx,pi rxx){
if(lx.val>=rx.val&&lx.val>=lxx.val+rxx.val) val=lx.val,pl=lx.pl,pr=lx.pr;
else if(rx.val>=lx.val&&rx.val>=lxx.val+rxx.val) val=rx.val,pl=rx.pl,pr=rx.pr;
else val=lxx.val+rxx.val,pl=lxx.pos,pr=rxx.pos;
}
void _min(pi2 lx,pi2 rx,pi lxx,pi rxx){
if(lx.val<=rx.val&&lx.val<=lxx.val+rxx.val) val=lx.val,pl=lx.pl,pr=lx.pr;
else if(rx.val<=lx.val&&rx.val<=lxx.val+rxx.val) val=rx.val,pl=rx.pl,pr=rx.pr;
else val=lxx.val+rxx.val,pl=lxx.pos,pr=rxx.pos;
}
};
struct node{
pi lmx,rmx,lmn,rmn;
pi2 mx,mn;
ll sum,tag;
void change(){
lmx.val*=-1,rmx.val*=-1,lmn.val*=-1,rmn.val*=-1;
mx.val*=-1,mn.val*=-1;
sum*=-1,tag*=-1;
}
};
struct seg{
node tr[N<<2];
void pushup(int u){
tr[u].lmx._max(tr[ls].sum,tr[ls].lmx,tr[rs].lmx);
tr[u].rmx._max(tr[rs].sum,tr[rs].rmx,tr[ls].rmx);
tr[u].mx._max(tr[ls].mx,tr[rs].mx,tr[ls].rmx,tr[rs].lmx);
tr[u].lmn._min(tr[ls].sum,tr[ls].lmn,tr[rs].lmn);
tr[u].rmn._min(tr[rs].sum,tr[rs].rmn,tr[ls].rmn);
tr[u].mn._min(tr[ls].mn,tr[rs].mn,tr[ls].rmn,tr[rs].lmn);
tr[u].sum=tr[ls].sum+tr[rs].sum;
}
void build(int u,int l,int r){
tr[u].tag=1;
if(l==r) {
ll a=max(0ll,y[l]);
ll b=min(0ll,y[l]);
tr[u]={{a,a?r:r-1},{a,a?l:l+1},{b,b?r:r-1},{b,b?l:l+1},{a,l,a?r:r-1},{b,l,b?r:r-1},y[l],1};
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
pushup(u);
}
void maketag(int u){
// pf("maketag %d\n",u);
tr[u]={tr[u].lmn,tr[u].rmn,tr[u].lmx,tr[u].rmx,tr[u].mn,tr[u].mx,tr[u].sum,tr[u].tag};
tr[u].change();
}
void pushdown(int u){
// pf("pushdown(%d),%lld\n",u,tr[u].tag);
if(tr[u].tag==1) return ;
maketag(ls),maketag(rs);
tr[u].tag=1;
}
void change(int u,int l,int r,int L,int R){
// pf("change(%d)\n",u);
if(R<L) return;
if(l>=L&&r<=R){
maketag(u);
return;
}
pushdown(u);
if(mid>=L) change(ls,l,mid,L,R);
if(mid+1<=R) change(rs,mid+1,r,L,R);
pushup(u);
}
ll ask(){
ll ans=tr[1].mx.val;
// pf("%lld change %lld %lld\n",ans,tr[1].mx.pl,tr[1].mx.pr);
change(1,1,cnt,tr[1].mx.pl,tr[1].mx.pr);
return ans;
}
}T;
ll ans;
signed main(){
#ifdef LOCAL
freopen("3.in","r",stdin);
freopen("my.out","w",stdout);
#else
freopen("hollow.in","r",stdin);
freopen("hollow.out","w",stdout);
#endif
sf("%d",&n);
x[0]=-1;
rep(i,1,n) {
cnt++;
sf("%lld%lld",&x[cnt],&y[cnt]);
if(x[cnt]==1) ans+=y[cnt];
if(x[cnt]==x[cnt-1]) {
y[cnt-1]+=y[cnt];
cnt--;
}
}
rep(i,1,cnt) y[i]*=(x[i]==0?1:-1);
T.build(1,1,cnt);
// rep(i,1,9) pf("%lld ",T.tr[i].mx.val);pf("\n");
// rep(i,1,9) pf("%lld ",T.tr[i].mn.val);pf("\n");
ans+=T.tr[1].lmx.val;
pf("%lld\n",ans);
// pf("pos %lld\n",T.tr[1].lmx.pos);
T.change(1,1,cnt,1,T.tr[1].lmx.pos);
rep(i,1,n) {
// rep(j,1,9) pf("%lld ",T.tr[j].mx.val);pf("\n");
// rep(j,1,9) pf("%lld ",T.tr[j].mn.val);pf("\n");
ans+=T.ask();
pf("%lld\n",ans);
}
}