NOIP2024T1求正确性证明，币关

#include<bits/stdc++.h>
#define us unsigned
#define ll long long
#define ci const int
#define cd const double
#define pb push_back
#define ppb pop_back
#define gc getchar
#define ppct __builtin_popcount
#define ctz __builtin_ctz
using namespace std;

int t;

int n;

string s_1,s_2,t_1,t_2;

int s1[101000],s2[101000],t1[101000],t2[101000];

int r1[101000],r2[101000];

void init(){
    cin>>n;
    cin>>s_1;
    for(int i=0;i<n;++i)
        s1[i+1]=s_1[i]=='0'?0:1;
    cin>>s_2;
    for(int i=0;i<n;++i)
        s2[i+1]=s_2[i]=='0'?0:1;
    cin>>t_1;
    for(int i=0;i<n;++i)
        t1[i+1]=t_1[i]=='0'?0:1;
    cin>>t_2;
    for(int i=0;i<n;++i)
        t2[i+1]=t_2[i]=='0'?0:1;
    t1[0]=0;t1[n+1]=0;
    t2[0]=0;t2[n+1]=0;
    memset(r1,0,sizeof r1);
    memset(r2,0,sizeof r2);
}
void sol(){
    vector<pair<int,int>> blk1,blk2;
    int pre=0;
    for(int i=1;i<=n+1;++i){
        if(t1[i]==1&&pre==0) pre=i;
        if(t1[i]==0&&pre!=0) {
            blk1.pb({pre,i-1});
            pre=0;
        }
    }
    pre=0;
    for(int i=1;i<=n+1;++i){
        if(t2[i]==1&&pre==0) pre=i;
        if(t2[i]==0&&pre!=0) {
            blk2.pb({pre,i-1});
            pre=0;
        }
    }
    for(auto b:blk1) sort(s1+b.first,s1+b.second+1);
    for(auto b:blk2) sort(s2+b.first,s2+b.second+1);
    for(auto b:blk1) {
        for(int i=b.first;i<=b.second;++i)
            r1[i]=b.second;
    }   
    for(auto b:blk2) {
        for(int i=b.first;i<=b.second;++i)
            r2[i]=b.second;
    }   
    for(int i=1;i<=n;++i){
        if(s1[i]==s2[i]) continue;
        else{
            if(s1[i]==0) {
                int nxo=lower_bound(s1+i,s1+r1[i]+1,1)-s1;
                if(nxo!=r1[i]+1){
                    swap(s1[i],s1[nxo]);
                }
            }
            else{
                int nxo=lower_bound(s2+i,s2+r2[i]+1,1)-s2;
                if(nxo!=r2[i]+1){
                    swap(s2[i],s2[nxo]);
                }
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
        if(s1[i]==s2[i]) ++ans;
    cout<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>t;
    while(t--){
        init();
        sol();
    }
    return 0;
}