一开始看到这题就很像模拟费用流，不过立马就放弃了，然后之后就再也没想过这个思路了。。。
正解是模拟费用流，先讲一下答案长什么样，把 \(0\) 的权值记为 \(1\) ， \(1\) 的权值记为 \(-1\) ，那么我们答案就是要选一段前缀和 \(k\) 段不相交的区间的最大值加上 \(1\) 的个数。
考虑为什么是 \(k\) 段不相交的区间，因为我们是区间翻转，所以一定能通过 \(k\) 次区间翻转，将前缀和这 \(k\) 段区间拼在一起。
然后 \(1\) 的权值记为 \(-1\) ，这是比较巧妙的一个点，这样你选的 \(0\) 间的 \(1\) 一定是无法造成贡献的，而我们把这些 \(1\) 的贡献减掉，最后加上所有 \(1\) 的贡献，很好的对应上了我们决策的方法，然后这题就做完了。
时间复杂度 \(O(k\log n)\)
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long LL;
using namespace std;
const int MAXN=2e5+10;
const LL inf=1e18;
int n;
struct itv {
LL l,r,s;
};
itv operator +(itv x,itv y) {
return {x.l,y.r,x.s+y.s};
}
bool operator <(itv x,itv y) {
return x.s<y.s;
}
struct ddl {
itv sum;
itv smi,smx;
itv lmi,rmi,lmx,rmx;
bool rev;
}tr[(MAXN<<2)];
void neww(int u,int x,int y) {
tr[u].smx=
tr[u].smi=
tr[u].lmi=
tr[u].rmi=
tr[u].lmx=
tr[u].rmx=
tr[u].sum={x,x,y};
}
ddl merge(ddl x,ddl y) {
ddl z;
z.smx=max(x.smx,y.smx);
z.smx=max(z.smx,x.rmx+y.lmx);
z.smi=min(x.smi,y.smi);
z.smi=min(z.smi,x.rmi+y.lmi);
z.lmx=max(x.lmx,x.sum+y.lmx);
z.rmx=max(y.rmx,x.rmx+y.sum);
z.lmi=min(x.lmi,x.sum+y.lmi);
z.rmi=min(y.rmi,x.rmi+y.sum);
z.sum=x.sum+y.sum;
z.rev=0;
return z;
}
void clere(int u) {
swap(tr[u].lmi,tr[u].lmx);
swap(tr[u].rmi,tr[u].rmx);
swap(tr[u].smi,tr[u].smx);
tr[u].lmi.s*=-1; tr[u].lmx.s*=-1;
tr[u].rmi.s*=-1; tr[u].rmx.s*=-1;
tr[u].smi.s*=-1; tr[u].smx.s*=-1;
tr[u].sum.s*=-1;
tr[u].rev^=1;
}
void psdn(int u) {
if(tr[u].rev) {
clere((u<<1));
clere((u<<1|1));
tr[u].rev=0;
}
}
void rev(int u,int l,int r,int x,int y) {
if(l>=x&&r<=y) {
clere(u);
return ;
}
int mid=(l+r)/2;
psdn(u);
if(x<=mid) rev((u<<1),l,mid,x,y);
if(y>mid) rev((u<<1|1),mid+1,r,x,y);
tr[u]=merge(tr[(u<<1)],tr[(u<<1|1)]);
}
void update(int u,int l,int r,int x,int y) {
if(l==r) {
neww(u,x,y);
return ;
}
int mid=(l+r)/2;
psdn(u);
if(x<=mid) update((u<<1),l,mid,x,y);
else update((u<<1|1),mid+1,r,x,y);
tr[u]=merge(tr[(u<<1)],tr[(u<<1|1)]);
}
int idx[MAXN],idy[MAXN],tot;
ddl query(int u,int l,int r,int x,int y) {
if(l>=x&&r<=y) return tr[u];
int mid=(l+r)/2;
psdn(u);
if(y<=mid) return query((u<<1),l,mid,x,y);
else if(x>mid) return query((u<<1|1),mid+1,r,x,y);
else return merge(query((u<<1),l,mid,x,y),query((u<<1|1),mid+1,r,x,y));
}
LL ans[MAXN];
signed main () {
scanf("%lld",&n);
LL ls=0,pp=0,j=0,da=0;
for(int i=1;i<=n;++i) {
LL oo=0,nu=0;
scanf("%lld%lld",&oo,&nu);
if(oo==0) {
update(1,1,n,i,nu);
pp+=nu;
}
else {
pp-=nu;
update(1,1,n,i,-nu);
ls+=nu;
}
if(pp>da) {
da=pp;
j=i;
}
}
ans[0]=da+ls;
if(j) rev(1,1,n,1,j);
for(int i=1;i<=n;++i) {
ddl ls=query(1,1,n,1,n);
ans[i]=ans[i-1];
if(ls.smx.s>=0) {
ans[i]+=ls.smx.s;
rev(1,1,n,ls.smx.l,ls.smx.r);
}
}
LL Q;
scanf("%lld",&Q);
for(int i=1;i<=Q;++i) {
LL x;
scanf("%lld",&x);
printf("%lld\n",ans[x]);
}
return 0;
}