http://cplusoj.com/d/senior/p/SS230928B
Old routine
Consider enums 0 and 2
m
+
j
+
m
i
n
(
f
a
m
?
g
a
j
,
f
b
m
?
g
b
j
)
\large m + j + min(fa_m-ga_j,fb_m-gb_j)
m + j + min(famgaj?,fbmgbj?)
Then split the min, discuss it according to the situation, move the items and merge the same ones
Take one of the situations as an example
f
a
m
?
g
a
j
≤
f
b
m
?
g
b
j
→
f
a
m
?
f
b
m
≤
g
a
j
?
g
b
j
\large fa_m-ga_j\le fb_m-gb_j \to fa_m-fb_m\le ga_j-gb_j
famgaj?≤fbmgbj?→famfbm?≤gajgbj?
m
+
f
a
m
+
(
?
g
a
j
+
j
)
\large m + fa_m + (-ga_j + j)
m + fam? + (?gaj? + j)
Just get a ds for maintenance later.
#include<bits/stdc + + .h>
using namespace std;
//#define int long long
inline int read(){<!-- -->int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){<!-- -->if(ch=='-')f=-1;ch=getchar();}while(ch>='0' & amp; & amp;ch <='9'){<!-- -->
x=(x<<1) + (x<<3) + (ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 5000010
//#define M
//#define mo
int n, m, i, j, k, T;
int sa[N], fa[N], ga[N], pa0[N], pa2[N];
int sb[N], fb[N], gb[N], pb0[N], pb2[N];
int ans, mx, p, pm;
char str[N];
void work(int *s, int *f, int *g, int *p0, int *p1) {<!-- -->
fill(s, s + n + 1, 0);
fill(f, f + n + 1, 0);
fill(g, g + n + 1, 0);
fill(p0, p0 + n + 1, 0);
fill(p1, p1 + n + 1, 0);
for(i=1; i<=n; + + i) if(str[i]=='1') s[i]=1;
for(i=1; i<=n; + + i) s[i] + =s[i-1];
for(i=1, j=0; i<=n; + + i) if(str[i]=='0')
f[ + + j]=s[i], p0[j]=i;
for(i=n, j=0; i>=1; --i) if(str[i]=='2')
g[ + + j]=s[i], p1[j]=i;
// reverse(g + 1, g + j + 1);
// reverse(p1 + 1, p1 + j + 1);
}
struct Tree_Bin {<!-- -->
int cnt[N<<1], i;
void mem() {<!-- -->
for(i=0; i<(N<<1); + + i) cnt[i]=-1e9;
}
void add(int op, int x, int y) {<!-- -->
x*=op; x + =N;
while(x<(N<<1)) cnt[x]=max(cnt[x], y), x + =x & amp;-x;
}
int que(int op, int x) {<!-- -->
x*=op;x + =N; int ans=-1e9;
while(x) ans=max(ans, cnt[x]), x-=x & amp;-x;
return ans;
}
}Bin1, Bin2;
signed main()
{<!-- -->
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
freopen("b.in", "r", stdin);
freopen("b.out", "w", stdout);
T=read();
while(T--) {<!-- -->
ans=0; Bin1.mem(); Bin2.mem();
scanf("%s", str + 1); n=strlen(str + 1);
work(sa, ga, fa, pa0, pa2);
scanf("%s", str + 1); // only 1
work(sb, gb, fb, pb0, pb2);
// cout<<"sa : "; for(i=1; i<=n; + + i) printf("%d ", sa[i]); printf("\
");
// cout<<"sb : "; for(i=1; i<=n; + + i) printf("%d ", sb[i]); printf("\
");
// cout<<"pa0 : "; for(i=1; i<=n; + + i) printf("%d ", pa0[i]); printf("\
");
// cout<<"pa2 : "; for(i=1; i<=n; + + i) printf("%d ", pa2[i]); printf("\
");
ans=min(sa[n], sb[n]);
for(i=1, mx=m=0; i<=n; + + i) {<!-- -->
if(pa0[i] & amp; & amp; pb0[i]) {<!-- -->
+ + mx;
ans=max(ans, mx + min(sa[n]-sa[pa0[mx]], sb[n]-sb[pb0[mx]])); //only 0 & amp; 1
}
if(pa2[i] & amp; & amp; pb2[i]) + + m;
}
//at most mx 0
reverse(fa + 1, fa + m + 1); reverse(pa2 + 1, pa2 + m + 1);
reverse(fb + 1, fb + m + 1); reverse(pb2 + 1, pb2 + m + 1);
\t\t
// cout<<"pa2 : "; for(i=1; i<=n; + + i) printf("%d ", pa2[i]); printf("\
");
// cout<<"pb2 : "; for(i=1; i<=n; + + i) printf("%d ", pb2[i]); printf("\
");
pm=m;
ans=max(ans, mx); // only 0
for(i=1, m=0, j=1; i<=n; + + i)
if(pa2[i] & amp; & amp; pb2[i]) {<!-- -->
+ + m;
while(j<=mx & amp; & amp; pa0[j]<pa2[m] & amp; & amp; pb0[j]<pb2[m]) {<!-- -->
Bin1.add(-1, ga[j]-gb[j], -ga[j] + j);
Bin2.add(1, ga[j]-gb[j], -gb[j] + j);
+ + j;
}
// printf("(%d[%d] %d)\
", m, pm-m + 1, j-1);
ans=max(ans, pm-m + 1 + min(sa[pa2[m]], sb[pb2[m]])); // only 1 & amp; 2
p=fa[m]-fb[m];
ans=max(ans, pm-m + 1 + fa[m] + Bin1.que(-1, p));
ans=max(ans, pm-m + 1 + fb[m] + Bin2.que(1, p));
}
ans=max(ans, m); //only 2
// printf("%d %d\
", mx, m);
printf("%d\
", ans);
}
return 0;
}