善于拆约束条件+合并相关项+DS维护：0928T2

http://cplusoj.com/d/senior/p/SS230928B

老套路了

考虑枚举0和2

$$m+j+min(f{a}_m-g{a}_j,f{b}_m-g{b}_j)$$

然后拆一下min，再分情况讨论一下，移项合并相同的

以其中一种情况为例

$$f{a}_m-g{a}_j\le f{b}_m-g{b}_j\to f{a}_m-f{b}_m\le g{a}_j-g{b}_j$$

$$m+f{a}_m+(-g{a}_j+j)$$

后面拿个ds维护即可

#include
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'&&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&-x; 
	}
	int que(int op, int x) {
		x*=op;x+=N;  int ans=-1e9; 
		while(x) ans=max(ans, cnt[x]), x-=x&-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("\n"); 
//		cout<<"sb : "; for(i=1; i<=n; ++i) printf("%d ", sb[i]); printf("\n"); 
//		cout<<"pa0 : "; for(i=1; i<=n; ++i) printf("%d ", pa0[i]); printf("\n"); 
//		cout<<"pa2 : "; for(i=1; i<=n; ++i) printf("%d ", pa2[i]); printf("\n"); 
		ans=min(sa[n], sb[n]); 
		for(i=1, mx=m=0; i<=n; ++i) {
			if(pa0[i] && pb0[i]) {
				++mx; 
				ans=max(ans, mx+min(sa[n]-sa[pa0[mx]], sb[n]-sb[pb0[mx]])); //only 0 & 1
			} 
			if(pa2[i] && 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); 
		
//		cout<<"pa2 : "; for(i=1; i<=n; ++i) printf("%d ", pa2[i]); printf("\n"); 
//		cout<<"pb2 : "; for(i=1; i<=n; ++i) printf("%d ", pb2[i]); printf("\n"); 
		pm=m; 
		ans=max(ans, mx); // only 0
		for(i=1, m=0, j=1; i<=n; ++i) 
			if(pa2[i] && pb2[i]) { 
				++m; 
				while(j<=mx && pa0[j]<pa2[m] && 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)\n", m, pm-m+1, j-1)			; 
				ans=max(ans, pm-m+1+min(sa[pa2[m]], sb[pb2[m]])); // only 1 & 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\n", mx, m); 
		printf("%d\n", ans); 
	}

	return 0;
}


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