CF2064E Mycraft Sand Sort Solution
这说明你的实力不足以上 Master。
唐题，但是我没有场切。
我们有以下的观察：
- 首先只能移动数的位置，数的颜色不能改变，因为如果改变了那么这种颜色对应的个数就变少了显然不同。
- 只有同色的数之间才可能可以互换位置，因为如果把两种不同颜色的数位置互换，那么最终他们落下之后上下的相对位置改变了，导致结果不同，非法。为什么是可能，因为比如对于
p=\{1,3,2,4\} ，c=\{1,1,2,1\} ，这种情况，你会发现他和p=\{4,3,2,1\} ，c=\{1,1,2,1\} 是不同的，你会感觉一个数不能交换到比它更大并且不同色的位置（当然这并不充分），因此有了下面的讨论。 - 最小的数不影响其他数的相同颜色位置的互换。这个有点难以说明，考虑一个例子：
p=\{3,1,4,2\} ，c=\{1,2,1,1\} ，你会发现除了1 ，其他数怎么交换都是合法的，因为其他数都大于1 ，不管怎么换都不会1 这一纵列上的相对颜色位置及个数。
然后其实就做完了。我们考虑维护相邻的极大同色块，这个可以并查集，从小到大枚举数，我们发现当前的数能换到的位置就是这个块的大小，所以答案累乘，然后因为这个数并不影响之后的数的放置，所以把这个数删去，如果这个数上下的数同色，那么合并，这个可以用链表维护，然后最后输出答案即可。
代码很好写。不知道为什么官解用了线段树，比较抽象。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const LL MOD = 998244353;
int n, A[N], C[N], nxt[N], pre[N]; pair<int, int> p[N];
int fa[N], sz[N];
int Find(int x) { return (fa[x] == x ? x : fa[x] = Find(fa[x])); };
void merge(int a, int b) {
int x = Find(a), y = Find(b);
if (x == y) return ;
fa[x] = y; sz[y] += sz[x]; sz[x] = 0;
}
int main() {
freopen(".in", "r", stdin); freopen(".out", "w", stdout);
ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int _; cin >> _;
while (_ --) {
cin >> n;
for (int i = 1; i <= n; i ++) { cin >> A[i]; p[i] = {A[i], i}; }
for (int i = 1; i <= n; i ++) cin >> C[i];
for (int i = 1; i <= n; i ++) fa[i] = i, sz[i] = 1;
sort(p + 1, p + 1 + n); LL Ans = 1; C[n + 1] = 114514191; nxt[0] = 1, pre[n + 1] = n;
for (int i = 1; i <= n; i ++) nxt[i] = i + 1, pre[i] = i - 1;
for (int i = 2; i <= n; i ++) if (C[i] == C[i - 1]) merge(i, i - 1);
for (int i = 1; i <= n; i ++) {
int u = p[i].second;
Ans = Ans * sz[Find(u)] % MOD; sz[Find(u)] --;
if (C[nxt[u]] == C[pre[u]]) merge(nxt[u], pre[u]);
nxt[pre[u]] = nxt[u]; pre[nxt[u]] = pre[u];
} cout << Ans << "\n";
}
return 0;
}