看了题面，感觉没有很难，不需要什么数据结构，只需要知道一个原理：对于某个序列，仅通过相邻位置交换，可以得出全排列。

定义s1区间[l,r1)，s2区间[l,r2)
①统计s1在[l,r1)区间内1的个数，定为count1，同时也能算出区间内2的个数为r1-l-count1
②统计s1在[l,r2)区间内1的个数，定为count2，同时也能算出区间内2的个数为r2-l-count2
③算出min1=min(count1,count2)，为s1和s2在相应区间内可相互抵消1的个数
④算出min2=min(r1-l-count1,r2-l-count2)，为s1和s2在相应区间内可相互抵消0的个数，叠加到输出答案上
⑤将左标l移动到min(r1,r2)
⑥右移min(r1,r2)，直到“碰壁”(遇到不可交换的位置)为止
⑦更新count1和count2
不断重复①-⑦，直到r1和r2均为n，即s1和s2遍历完毕。

这里的小tip在于count1和count2的更新方法，不要每次移动完后从0开始重新计算，这样大概率会超时，方法(以r1<=r2为例，r1>r2同理)：
①若r1==r2，意味着s1和s2在[0,r1)或[0,r2)皆处理完毕，count1=count2=0
②若r1<r2且count1>=count2，意味着s2在[l,r2)内的1会被s1全部抵消，因此count1=count2=0
③若r1<r2且count1<count2，意味着s2在[l,r2)内的1没又会被s1全部抵消，此时——
a、先做count2-=min1，即把能被s1抵消掉的1减掉
b、若(min1+min0)<(r1-l)，即区间内1和0不能（通过若干交换操作后）完全匹配，需要让s2的r1-l-(min1+min0)个1“含冤死去”，即count2-=r1-l-(min1+min0)
c、更新count1=0

应该是O(n)吧。

#include <iostream>
#include <string>
using namespace std;

int T,n,l,r1,r2,ss;
bool s1[100005],s2[100005],t1[100005],t2[100005];
int count1,count2;//统计s1和s2在区间[l,r)内1的数量 

void deal(){
	l=0,r1=0,r2=0,count1=0,count2=0,ss=0;
	//count1+=s1[0],count2+=s2[0];
	int min1=0;//区间内s1和s2数字1的最少量 
	int min0=0;//区间内s1和s2数字0的最少量
	while(l<n){
		//右标小的向右移动，直到卡住，并统计相应的1 
		if(r1<=r2){
			while(t1[r1]&&r1<n)count1 += s1[r1++];
			if(r1==l)count1 += s1[r1++];//被卡住了，没动过，就移动一下下 
		}
		else{
			while(t2[r2]&&r2<n)count2 += s2[r2++];
			if(r2==l)count2 += s2[r2++];//被卡住了，没动过，就移动一下下 
		}
		//计算区间[l,r)内s1和s2数字1和数字0的最少量
		min1=min(count1,count2);
		min0=min(r1-l-count1,r2-l-count2);
		ss+=min1+min0;//通过若干次交换操作后，0和1有min1+min0个能完全匹配消去 
		//cout<<"l:"<<l<<" r1:"<<r1<<"  r2:"<<r2<<" count1:"<<count1<<"  count2:"<<count2<<" min1:"<<min1<<"  min0:"<<min0<<"  ss:"<<ss<<endl;
		//更新count1和count2
		if(r1<r2){//左标即将变为r1
			if(count1>=count2)count2=0;//s2区间[l,r2)内的1全部用掉 
			else{//s2区间[l,r2)内的1没能全部用掉 
				count2-=min1;//先抵消掉共同的1 
				if((min1+min0)<(r1-l)){//s1区间[l,r1)内的0不能全部抵消，要用s2的一些1来顶 
					count2-=r1-l-(min1+min0);
				}
			}
			count1=0;
		}else if(r1>r2){
			if(count1<=count2)count1=0;//s1区间[l,r1)内的1全部用掉 
			else{//s1区间[l,r1)内的1没能全部用掉 
				count1-=min1;//先抵消掉共同的1 
				if((min1+min0)<(r2-l)){//s2区间[l,r2)内的0不能全部抵消，要用s1的一些1来顶 
					count1-=r2-l-(min1+min0);
				}
			}
			count2=0;
			//count1 =max(0,count1-min1);
		}else{count1=0;count2=0;}//r1和r2相等，左标右移，1数统计归零 
		//cout<<" count1:"<<count1<<"  count2:"<<count2<<endl;
		//以较小的r为基准，更新左区间
		l=min(r1,r2);
	}
}

int main(){
	cin>>T;
	for(int i=0;i<T;i++){
		cin>>n;
		string st;
		cin>>st;
		for(int j=0;j<n;j++)s1[j]=st[j]-'0';
		cin>>st;
		for(int j=0;j<n;j++)s2[j]=st[j]-'0';
		cin>>st;
		for(int j=0;j<n;j++)t1[j]=st[j]-'0';
		cin>>st;
		for(int j=0;j<n;j++)t2[j]=st[j]-'0';
		deal();
		cout<<ss<<endl;
	}
	return 0;
}