求调

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int T;
struct segment
{
    int id;
    int l,r;
    int num0,num1;
}a1[maxn],a2[maxn];
int n,cnt1,cnt2,ans;
int hash1[maxn],hash2[maxn];
char s1[maxn],s2[maxn],c1[maxn],c2[maxn];
int main()
{
    ios::sync_with_stdio(0);
    cin>>T;
    while(T--)
    {
        memset(a1,0,sizeof(a1));
        memset(a2,0,sizeof(a2));
        memset(hash1,0,sizeof(hash1));
        memset(hash2,0,sizeof(hash2));
        cnt1=cnt2=ans=0;
        cin>>n;
        for (int i=1;i<=n;++i) cin>>s1[i];
        for (int i=1;i<=n;++i) cin>>s2[i];
        for (int i=1;i<=n;++i) cin>>c1[i];
        for (int i=1;i<=n;++i) cin>>c2[i];
		int lst=0,cur0=0,cur1=0;
		for (int i=1;i<=n;++i)
		{
		    if (s1[i]=='0') cur0++;
		    if (s1[i]=='1') cur1++;
		    if (i==1&&c1[i]=='0')
		    {
		        a1[++cnt1].l=a1[cnt1].r=1;
		        a1[cnt1].id=cnt1;
		        a1[cnt1].num0=cur0;
		        a1[cnt1].num1=cur1;
		        cur0=0,cur1=0;
		        lst++;
		        continue;
		    }
		    if (c1[i]=='0') 
		    {
		        a1[++cnt1].l=lst+1,a1[cnt1].r=i-1;
		        a1[cnt1].id=cnt1;
		        a1[cnt1].num0=cur0;
		        a1[cnt1].num1=cur1;
		        a1[++cnt1].l=a1[cnt1].r=i;
		        a1[cnt1].id=cnt1;
		        if (s1[i]=='0')
		        {
		            a1[cnt1-1].num0=a1[cnt1-1].num0-1;
		            a1[cnt1].num0=1;
		            a1[cnt1].num1=0;
		        }
		        else 
		        {
		            a1[cnt1-1].num1=a1[cnt1-1].num1-1;
		            a1[cnt1].num0=0;
		            a1[cnt1].num1=1;
		        }
		        lst=i,cur0=0,cur1=0;
		    }
		}  
		if (lst<n)
	    {
	    	a1[++cnt1].l=lst+1,a1[cnt1].r=n;
	    	a1[cnt1].id=cnt1;
	    	a1[cnt1].num0=cur0;
	    	a1[cnt1].num1=cur1;
	    }
	    lst=0,cur0=0,cur1=0;
	    for (int i=1;i<=n;++i)
	    {
	        if (s2[i]=='0') cur0++;
	        if (s2[i]=='1') cur1++;
	        if (i==1&&c2[i]=='0')
	        {
	            a2[++cnt2].l=a2[cnt2].r=1;
	            a2[cnt2].id=cnt2;
	            a2[cnt2].num0=cur0;
	            a2[cnt2].num1=cur1;
	            cur0=0,cur1=0;
	            lst++;
	            continue;
	        }
	        if (c2[i]=='0') 
	        {
	            a2[++cnt2].l=lst+1,a2[cnt2].r=i-1;
	            a2[cnt2].id=cnt2;
	            a2[cnt2].num0=cur0;
	            a2[cnt2].num1=cur1;
	            a2[++cnt2].l=a2[cnt2].r=i;
	            a2[cnt2].id=cnt2;
	            if (s2[i]=='0')
	            {
	                a2[cnt2-1].num0=a2[cnt2-1].num0-1;
	                a2[cnt2].num0=1;
	                a2[cnt2].num1=0;
	            }
	            else 
	            {
	                a2[cnt2-1].num1=a2[cnt2-1].num1-1;
	                a2[cnt2].num0=0;
	                a2[cnt2].num1=1;
	            }
	            lst=i,cur0=0,cur1=0;
	        }
	    }
		if (lst<n)
	    {
	    	a2[++cnt2].l=lst+1,a2[cnt2].r=n;
	    	a2[cnt2].id=cnt2;
	    	a2[cnt2].num0=cur0;
	    	a2[cnt2].num1=cur1;
	    }
	    /*
        for (int i=1;i<=cnt1;++i)
        {
        	cout<<a1[i].id<<"\n";
        	cout<<a1[i].l<<' '<<a1[i].r<<"\n";
        	cout<<a1[i].num0<<' '<<a1[i].num1<<"\n";
        	cout<<"\n";
        }
        cout<<"\n";
        for (int i=1;i<=cnt2;++i)
        {
        	cout<<a2[i].id<<"\n";
        	cout<<a2[i].l<<' '<<a2[i].r<<"\n";
        	cout<<a2[i].num0<<' '<<a2[i].num1<<"\n";
        	cout<<"\n";
        }
        */
        for (int i=1;i<=cnt1;++i)
        {
        	for (int j=a1[i].l;j<=a1[i].r;++j)
        	{
        		hash1[i]=a1[i].id;
        	}
        }
        for (int i=1;i<=cnt2;++i)
        {
        	for (int j=a2[i].l;j<=a2[i].r;++j)
        	{
        		hash2[i]=a2[i].id;
        	}
        }        
		for (int i=1;i<=n;++i)
		{
			int id1=hash1[i];
			int id2=hash2[i];
			if (a1[id1].num0>0&&a2[id2].num0>0) 
			{
				a1[id1].num0--;
				a2[id2].num0--;
				ans++;
				//cout<<ans<<' ';
			}
			else if (a1[id1].num1>0&&a2[id2].num1>0)
			{
				a1[id1].num1--;
				a2[id2].num1--;
				ans++;
				//cout<<ans<<' ';
			}
		}
		cout<<ans<<"\n";
    }
}
/*
1
6
011101
111010
111010
101101
*/