F1. Array Shuffling

题意：
给你长度为 $n$ 的数组 $a$ ，请你用 $a$ 的排列构造出一个新的数组 $b$ ，你可以任意交换数组 $b$ 上的任意两个元素，要求用数组 $b$ 通过交换，复原数组 $a$ 所需要的次数最多，构造出这个 $b$
思路：
一个结论：如果 $b_i$ 可以移动到 $b_j$ 的位置，则可以将点 $\sim j$ 连一条边，连好边后可以得到 $c n t$ 个环，最终的操作数为 $n ? c n t$
假设我们有 $[1, 2, 3, 4, 5, 6]$ 变为 $[6, 1, 2, 3, 4, 5]$
在这里插入图片描述

一个环，所以操作数 $6 ? 1$ 次
那么，只要我们有最少的环，就可以得到最大的操作次数
那么环有多少个？
如果一个环中，一个元素在环中出现的两次
也就是有环
$\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5\rightarrow 1$
其中 $a_1=a_3$
那么我们可以将原本的环拆分成两个小环
$\rightarrow 2\rightarrow 1\\3\rightarrow 4\rightarrow 5\rightarrow 3$
所以一个最小的环中，不能出现相同的元素。那么我们环的数量也就是数组中出现最多的数字出现次数
该如何构造？
每次只需要选择尽可能多的数字放进同一个集合中，认为这些数字属于同一个环，将这些数字错位即可
注意错位的时候要尽可能的按照某种单调性来错位，来避免与其他环上的数字混合
这里提供一种构造方法：在同一个集合上的数字，将最小的数字移动到第二小的数字的位置，将第二小的数字移动到第三小的数字的位置，…，将最大的数字移动到最小的数字的位置

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=4e5+7;
int a[maxn],vis[maxn];
vector<int>v[maxn];
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++) vis[i]=0,v[i].clear();
		int mx=0;
		for(int i=1;i<=n;i++) 
		{
			scanf("%d",&a[i]);
			vis[a[i]]++;
			mx=max(mx,vis[a[i]]);
			v[vis[a[i]]].pb(a[i]);
		}
		for(int i=1;i<=mx;i++) sort(v[i].begin(),v[i].end());
		for(int i=1;i<=n;i++)
		{
			int u=vis[a[i]];vis[a[i]]--;
			int num=upper_bound(v[u].begin(),v[u].end(),a[i])-v[u].begin();
			if(num==v[u].size()) printf("%d ",v[u][0]);
			else printf("%d ",v[u][num]);
		}
		puts("");
	}
}

F2. Checker for Array Shuffling

题意：
就是请你来给 $F 1$ 写一个 $s p j$ 程序
思路：
如上，如果满足最大次数的要求，则应该有最小数量的环，也就是所有的环都应该是互相不干扰的
那么我们可以给每个环上都删去一条边，再判断环是否还存在，如果图中依然存在环，那么说明构造不符合要求，否则，符合要求
我们可以对将除了最大到最小的边删去，其他边依然连接，对剩余图跑 $d f s$ 来判断是否还存在环

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int a[maxn],b[maxn],vis[maxn];
vector<int>v[maxn],edge[maxn];
int inst[maxn],vv[maxn],flag;
void dfs(int u)
{
	for(auto i:edge[u])
	{
		if(inst[i])
		{
			flag=0;return;
		}
		if(vv[i]) continue;
		vv[i]=1;inst[i]=1;
		dfs(i);
		inst[i]=0;
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int mx=0,num;
		for(int i=1;i<=n;i++) 
		{
			vis[i]=0;v[i].clear();
			edge[i].clear();
			inst[i]=0,vv[i]=0;
			scanf("%d",&a[i]);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&b[i]);
			vis[b[i]]++;
			if(vis[b[i]]>mx)
			{
				mx=vis[b[i]];num=b[i];
			}
			v[b[i]].push_back(i);
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<v[i].size();j++)
			{
				edge[v[i][j-1]].push_back(v[i][j]);
			}
		}
		for(int i=1;i<=n;i++)
			if(b[i]!=num) edge[i].push_back(*v[a[i]].begin());
		flag=1;
		for(int i=1;i<=n;i++)
			if(vv[i]==0) dfs(i);
		if(flag) puts("AC");
		else puts("WA");
	}
}

H. Zigu Zagu

题意：
给你一个 $01$ 串，有多次查询 $l, r$ ，请你回答将这个区间的子串完全删除需要最少几次操作
删除的规则是：

可以一次性删除任意长度的 $01$ 交替的连续子串
删除后的字符串左右会拼接在一起形成新字符串

思路：
为了尽可能的操作最少次数，我们当然希望有最长的 $01$ 交替串。但对于那些连续串，也不得不逐一删除，因此我们只需要统计出现了多少的的连续串即可，将这些连续串删除掉，剩余的串一定可以凑成一条交替串，于是，只要再额外的操作一次就行了
但是实际上我们并不需要完全逐个删除重复子串，即便是重复子串，也会有边界交替的位置，在这些位置其实每次可以同时删除一整对的 $01$ 或 $10$ ，所以消除掉所有重复子串的数量其实是删除两种重复串数量的最大值
于是用前缀和维护即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+7;
int n,q;
char s[maxn];
int sum[maxn][3];
int main()
{
	scanf("%d%d",&n,&q);
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		sum[i][0]=sum[i-1][0]+(s[i]=='0' && s[i]==s[i-1]);
		sum[i][1]=sum[i-1][1]+(s[i]=='1' && s[i]==s[i-1]);
	}
	while(q--)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		printf("%d\n",max(sum[r][0]-sum[l][0],sum[r][1]-sum[l][1])+1);
	}
}