赛时做法：枚举下标，用2个单调队列存储当前可交换且2个串不同的位置。

然后当当前2串相同时：ans++，检查2个队列开头是否满足某个位置可交换，如果可以，出队并把当前位置入队（把11和之前的某个01换）。

否则：检查某一个队列的开头，如可以换，ans+=2（相当于换01和10）。

赛后代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100007;
int q[2][N],c[2][N],s[2][N],t[2][N],*bg[2],*ed[2];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin>>T;
	while(T-->0){
		int n,ans=0;
		cin>>n;
		char ch;
		for(int j=0;j<2;j++) for(int i=1;i<=n;i++) cin>>ch,s[j][i]=(ch=='1');
		for(int j=0;j<2;j++) for(int i=1;i<=n;i++) cin>>ch,t[j][i]=(ch=='0');
		for(int j=0;j<2;j++) for(int i=1;i<=n;i++) c[j][i]=c[j][i-1]+t[j][i];
		for(int j=0;j<2;j++) for(int i=1;i<=n;i++) if(t[j][i]) c[j][i]=i+0x3f3f3f3f;
		bg[0]=ed[0]=q[0],bg[1]=ed[1]=q[1];
		for(int i=1;i<=n;i++){
			for(int j=0;j<2;j++) while((bg[j]!=ed[j])&&!(c[0][i]==c[0][*bg[j]]||c[1][i]==c[1][*bg[j]])) bg[j]++;
			if(s[0][i]==s[1][i]){
				for(int j=0;j<2;j++) if((bg[j^s[0][i]]!=ed[j^s[0][i]])&&(c[j^s[0][i]][i]==c[j^s[0][i]][*bg[j]])){
					bg[j]++;
					*(ed[j]++)=i;
					break;
				}
				ans++;
			}else{
				if(bg[s[0][i]]!=ed[s[0][i]]){
					bg[s[0][i]]++;
					ans+=2;
				}else *(ed[s[1][i]]++)=i;
			}
		}
		cout<<ans<<'\n';
	}
}