交换如果相等长度和总和
3a51_
·
·
题解
::::info[Hint 1]
尝试寻找不变量。
::::
::::info[Hint 2]
尝试对于所有满足上述条件的 $a,b$ 寻找操作方案，即证明充要。
::::
::::info[Hint 3]
操作次数的限制较为宽松，尝试每步使用形如 `1000...000` 和 `000...0001` 的操作归位一个 `1`，以此构造出操作次数 $\leq n$ 的方案。
::::
::::info[Hint 4]
尝试对序列做一些变换使得操作次数 $\leq \lfloor\frac{n}{2}\rfloor$。
::::
::::info[Solution]
先阅读所有提示。
显然操作不能改变 `1` 的个数。
发现操作不会改变所有 `1` 的下标和。证明是简单的，假设交换的区间为 $[l,r]$ 和 $[l',r']$ 且满足 $r<l'$，那么交换过后 $[l',r']$ 内每个 `1` 下标减少了 $l'-l$，$[l,r]$ 内每个 `1` 下标增加了 $l'-l$，故 `1` 的下标和相等。
合理猜测上述条件充要。尝试构造方案。
手搓几次操作，观察到操作长度为 $2$ 的区间等价于将一个 `1` 向后挪一位，另一个 `1` 向前挪一位。于是不难想到一个思路，考虑每次操作归位一个 `1`，使用 `000...0001` 和 `1000...000` 进行操作，等价于一个 `1` 往后挪若干位，另一个 `1` 往前挪若干位。每次挑选一个 `1` 归位即可。
然而，上述做法操作次数最大可以达到 $n$，需要优化。观察到当 `1` 的个数超过 $\lfloor\frac{n}{2}\rfloor$ 时操作次数才有可能超出限制，而此时 `0` 的个数一定不超过 $\lfloor\frac{n}{2}\rfloor$，故只需把原序列按位翻转即可。
于是，我们对于每一个满足 `1` 下标和相等且 `1` 数量相等的 $a$ 和 $b$ 都能构造出方案，即证明了其充要。
实现时，先判掉无解，然后将两序列的 `1` 一一匹配，分为往左挪和往右挪两类，一次挪一个即可。记得输出时，把靠右的区间输出在后面。
::::
::::success[Code]
```cpp
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define _rep(i,a,b) for(int i=(a);i>=(b);i--)
#define pi pair<int,int>
#define arr(a) array<int,(a)>
#define F fflush(stdout)
#define RE return puts("No"),void()
#define cases(_) while((_)--) solve();
using namespace std;
const int N=200005;
int _=1,n,a[N],b[N],s;
vector<arr(3)> ans;
vector<pi> pre,suf;
vector<int> va,vb;
void solve(){
scanf("%d",&n),s=0,ans.clear(),pre.clear(),suf.clear(),va.clear(),vb.clear();
rep(i,1,n){
scanf("%d",&a[i]);
if(a[i]) va.push_back(i),s+=i;
}
rep(i,1,n){
scanf("%d",&b[i]);
if(b[i]) vb.push_back(i),s-=i;
}
int m=(int)va.size();
if(m!=(int)vb.size() || s) RE;
if(m>n/2){
rep(i,1,n) a[i]^=1,b[i]^=1;
va.clear(),vb.clear();
rep(i,1,n){
if(a[i]) va.push_back(i);
if(b[i]) vb.push_back(i);
}
m=n-m;
}
m--;
rep(o,0,m){
if(va[o]<vb[o]) pre.push_back({va[o],vb[o]});
else if(va[o]>vb[o]) suf.push_back({va[o],vb[o]});
}
int l=(int)pre.size()-1,r=0;
while(l!=-1 && r!=(int)suf.size()){
int pl=pre[l].second-pre[l].first,pr=suf[r].first-suf[r].second,cur=min(pl,pr);
ans.push_back({pre[l].first,suf[r].first-cur,cur});
pre[l].first+=cur,suf[r].first-=cur;
if(pl==cur) l--;
if(pr==cur) r++;
}
puts("Yes");
printf("%d\n",(int)ans.size());
for(arr(3) t:ans){
if(t[0]+t[2]<t[1]) printf("%d %d %d %d\n",t[0],t[0]+t[2],t[1],t[1]+t[2]);
else printf("%d %d %d %d\n",t[1],t[1]+t[2],t[0],t[0]+t[2]);
}
}
signed main(){
scanf("%d",&_);
cases(_);
return 0;
}
```
::::