【学习笔记】CF1895G Two Characters, Two Colors
感谢grass8sheep提供的思路。
首先，我们可以用$DP$解决这个问题。
设$f_{i,j}$表示前$i$个数中有$j$个为$1$的位置为红色的最大价值。则转移如下：
- $f_{i,j}\gets f_{i-1,j}+b_i$
- 若$s_i=1$，有转移$f_{i,j}\gets f_{i-1,j-1}+r_i$
- 若$s_i=0$，有转移$f_{i,j}\gets f_{i-1,j}-j+r_i$
初始$f_{0,j}=0$。
考虑差分序列，记作$\{d_i\}$。则$s_i=1$的转移等价于，对于一段连续的满足$ 但是打表可以发现，答案不是凸的，也就是说$d_i$不具有单调性。事实上有一个结论：每次结束后，将$d_i$按从大到小排序，这并不会影响答案。因此用平衡树维护即可，操作一对应区间平移；操作二对应前缀减$1$，然后将差值为一的两个连续段交换。 复杂度$O(n\log n)$。 关于结论的证明：设$dp_j$表示考虑完前$i$个数后选了$j$个$1$的最大价值，$dp_{j}=a$，$dp_{j+1}=a+b$，$dp_{j+2}=a+2b+1$。设之后的方案中选了$x$个$0$，那么我们要让$dp_i-ix$最大。发现交换了$d_{j+1}$和$d_{j+2}$后$j+1$仍然不可能成为答案。（考虑是一条直线来截每个点使得截矩最大，因为斜率是整数，而相邻两点间斜率之差又不超过$1$，因此不可能截到中间那个点） 因为每次操作是前缀减$1$，所以交换的两个段之差不会超过$1$，因此结论是正确的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
using namespace std;
const int N=4e5+5;
int T,n,tot,rt;
ll r[N],b[N];
string str;
mt19937 gen(time(0));
struct node{
int fix,l,r,sz;
ll tag,val;
}t[N];
void pushup(int p){
t[p].sz=t[t[p].l].sz+t[t[p].r].sz+1;
}
int newnode(ll val){
tot++;
t[tot].fix=gen(),t[tot].l=t[tot].r=t[tot].tag=0,t[tot].sz=1,t[tot].val=val;
return tot;
}
void add(int p,ll x){
if(!p)return;
t[p].val+=x,t[p].tag+=x;
}
void pushdown(int p){
if(t[p].tag)add(t[p].l,t[p].tag),add(t[p].r,t[p].tag),t[p].tag=0;
}
int merge(int x,int y){
if(!x||!y)return x+y;
if(t[x].fix>t[y].fix){
pushdown(x);
t[x].r=merge(t[x].r,y);
pushup(x);
return x;
}
else{
pushdown(y);
t[y].l=merge(x,t[y].l);
pushup(y);
return y;
}
}
void split0(int rt,int &x,int &y,ll val){
if(!rt){
x=y=0;
return;
}
pushdown(rt);
if(t[rt].val>=val){
x=rt;
split0(t[x].r,t[x].r,y,val);
pushup(x);
}
else{
y=rt;
split0(t[y].l,x,t[y].l,val);
pushup(y);
}
}
void split1(int rt,int &x,int &y,int val){
if(!rt){
x=y=0;
return;
}
pushdown(rt);
if(t[t[rt].l].sz+1<=val){
x=rt;
split1(t[x].r,t[x].r,y,val-t[t[rt].l].sz-1);
pushup(x);
}
else{
y=rt;
split1(t[y].l,x,t[y].l,val);
pushup(y);
}
}
int rs(int x){
while(t[x].r)x=t[x].r;
return x;
}
int ls(int x){
while(t[x].l)x=t[x].l;
return x;
}
int cnt;
ll c[N];
void dfs(int x){
pushdown(x);
if(t[x].l)dfs(t[x].l);
c[++cnt]=t[x].val;
if(t[x].r)dfs(t[x].r);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>T;
while(T--){
cin>>n>>str;
for(int i=1;i<=n;i++)cin>>r[i];
for(int i=1;i<=n;i++)cin>>b[i];
rt=tot=0;ll sm=0;int c1=0;
for(int i=1;i<=n;i++){
if(r[i]<=b[i]){
sm+=b[i];
continue;
}
else if(str[i-1]=='1'){
c1++,sm+=b[i];
int x,y;
split0(rt,x,y,r[i]-b[i]);
rt=merge(x,merge(newnode(r[i]-b[i]),y));
}
else{
sm+=r[i];
int x,y;
split1(rt,x,y,min(1ll*c1,r[i]-b[i]));
if(!x||!y){
add(x,-1);
rt=x+y;
}
else{
int _x=rs(x),_y=ls(y);
if(t[_x].val==t[_y].val){
ll val=t[_x].val;
int a,b,c,d;
split0(x,a,b,val+1);
split0(y,c,d,val);
add(a,-1),add(b,-1);
rt=merge(merge(a,c),merge(b,d));
}
else{
add(x,-1);
rt=merge(x,y);
}
}
}
}
cnt=0,dfs(rt);
ll res=sm;
for(int i=1;i<=c1;i++){
sm+=c[i],res=max(res,sm);
}
cout<<res<<"\n";
}
}
【学习笔记】CF1895G Two Characters, Two Colors