题解：CF2118F Shifts and Swaps
yh2023zlh
·
·
题解
好题，简单清新，考验洞悉。
遇到“操作可达性”的题，要看透操作的本质。
首先，循环左移操作意味着一个串和它所有循环移位都本质相同。
到这里，如果你仔细想想，你就会发现数值在数组中的下标并不重要，重要的是相对下标。因为我们只关心相对位置而不是绝对位置，所有不妨把数组变为环。
再考虑下操作二。就是相等或相差 1 的数不能交换，其他都能随便排列。这个可以利用增量方法思考。
先考虑 1，把数字 1 在环上的位置标出来。
然后考虑 2，你会发现原本 1 的位置变成了“隔板”，隔板间的 2 数量守恒，不会逾越隔板。
于是，$i$ 总是对 $i+1$ 进行**划分**，这是一个树状物。
:::info[如何想到]
其实这样的结构大概率都是树状物。例如括号序列，上层括号套下层括号，**内外互不影响，把节点不断细分**。
这题很有特征，两个 $i$ 内的 $i+1$ 对外面不会有影响，而且 $i$ 能把 $i+1$ 分成若干不交的集合。
:::
用树来描述，就是对于每个数值为 $i$ 的位置，向后找，遇到 $i+1$ 则建边，遇到 $i$ 则停止。这样，所有“划分”的集合都顺着树结构变成了某个节点的子节点。建图有很容易的 $O(n)$ 方法。
---
判断两者相同与否可以用树哈希。但是我们发现这题的树是有序的，我们必须按顺序 dfs 子节点。有个哈希方法如下：
- 用字符串哈希的方式依次哈希所有子节点。
- 给上一步结构乘上第 $sz_u$ 个质数作为节点哈希值。其中 $sz_u$ 为 $u$ 的子树大小。
- 无模数自然溢出。
最后，森林中的树要按顺序排成一排，但是可以循环轮换。我们取所有树哈希值的[最小表示](https://www.luogu.com.cn/problem/P13270)即可。
时间复杂度 $O(n\ln n)$。
:::success[代码]
```cpp
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
using namespace std;
const int N=5e5+7,S=1e7+7,mod=998244353;
const ull base=13331;
int T,n,m,head[N],to[N*2],last[N*2],u,v,idx;
int pr[S],a[N],b[N],sz[N],hack;
ull tmp[N*2];
bool is_p[S];
vector<int> d[N];
void add(int u,int v){
++idx;
to[idx]=v,last[idx]=head[u],head[u]=idx;
}
ull dfs(int u,int fa){
sz[u]=1;
ull ans=1145141;
for(int i=head[u];i;i=last[i]){
ans=ans*base+dfs(to[i],u),sz[u]+=sz[to[i]];
}
ans*=pr[sz[u]];
return ans;
}
ull func(){
for(int i=1;i<=n;i++){
cin>>a[i],d[a[i]].push_back(i);
}
for(int i=1;i<m;i++){
int p=-1,k=d[i].size();
while(p+1<d[i+1].size()&&
d[i+1][p+1]<d[i][0]) p++;
for(int j=0;j<k-1;j++){
while(p+1<d[i+1].size()&&d[i+1][p+1]<d[i][j+1]){
p++;
add(d[i][j],d[i+1][p]);
}
}
p++;
while(p<d[i+1].size()){
add(d[i][k-1],d[i+1][p]),p++;
}
p=-1;
while(p+1<d[i+1].size()&&
d[i+1][p+1]<d[i][0]){
p++;
add(d[i][k-1],d[i+1][p]);
}
}
int k=d[1].size(),id=0,x=0;
for(int i=0;i<k;i++){
tmp[i]=dfs(d[1][i],0),tmp[i+k]=tmp[i];
}
for(int i=1;i<k;i++){
int j=0;
while(j<k&&tmp[i+j]==tmp[id+j]) j++;
if(j==k) break;
if(tmp[i+j]<tmp[id+j]) x=id,id=i,i=max(i,x+j);
else i+=j;
}
ull ans=0;
for(int i=0;i<k;i++) ans=ans*base+tmp[id+i];
for(int i=1;i<=n;i++) head[i]=0;
for(int i=1;i<=m;i++) d[i].clear();
for(int i=1;i<=idx;i++) to[i]=last[i]=0;
idx=0;
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
for(int i=2;i<S;i++){
if(!is_p[i]) pr[++m]=i;
for(int j=1;j<=m&&pr[j]*i<S;j++){
is_p[pr[j]*i]=1;
if(i%pr[j]==0) break;
}
}
cin>>T;
while(T--){
cin>>n>>m,++hack;
if(func()==func()) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
```
:::