题目链接：https://zhixincode.com/contest/14/problem/I?problem_id=211
样例输入 1
3 5 2 1 1 2 1 2 1 1 2 3 2 1
样例输出 1
27 9 6
题解：
首先，比较明显地是，每进行一次操作 $1$，对于目前的卡牌分配情况的种数，其中的 $1/3$ 种是被撤掉位子的人留下，其余 $2/3$ 种是“擂主”留下。
而且，进行完一次操作 $1$ 后，“擂主”位子上分配到的卡牌，石头剪刀布的数目比依然是均等的，因此不会影响后面继续进行操作 $1$ 时的 $1/3 : 2/3$ 的情况种数的比例。
所以，最初没有撤掉过座位，每个人使得他们留下的卡牌分配种数都是 $3^n$ 种。然后一旦进行一次操作 $1$，被撤掉位子的人他的种数就变为原来的 $1/3$，擂主则变为原来的 $2/3$。
那么，一种最朴素的做法就是，保存下所有操作 $1$，对于每次操作 $2$ 查询，都遍历一遍其前面的所有操作 $1$，从 $3^n$ 一直不断地乘以 $1/3$ 或 $2/3$ 直到算出目前的答案。
例如题目的样例，第 $1$ 个人留下来的情况，可以表示成一个简单图表可以如下：
但是这样的时间复杂度是 $O(m^2)$ 的，我们要进行一定的优化。
对于一名选手，他如果经过 $a$ 次主场作战，$b$ 次客场作战，那么其对应的查询答案就是 $(frac{2}{3})^a cdot (frac{1}{3})^b cdot 3^n$。
也就是说，我们要维护每个选手的主场作战次数和客场作战的次数。
我们对于每个座位，不妨将其看做一个集合，集合内的存储的是可能坐在这个位置上的选手的编号。
那么，每次操作 $1$ 相当于合并两个集合，如果我们对每个选手 $p$ 用两个属性 $p.a$ 和 $p.b$ 分别记录其进行的主场和客场比赛数目。
那么我们可以用带权并查集来进行维护：
首先我们知道，任何一个节点，它自己外加它的所有子孙，合起来作为一个集合。我对每个节点 $v$ 都设 $Delta a[v]$ 和 $Delta b[v]$，表示其所统领的整个集合（也就是，该节点本身，以及其所有子孙节点，共同组成的集合），这个集合内的所有节点的主场数目都加上 $Delta a[v]$，客场数目都加上 $Delta b[v]$。
那么，对于并查集的合并（把一个根节点接到另一个根节点下）和查询操作（把一个节点一点点往上爬直到接到树根下为止），我们都可以比较自然的得出如何维护 $Delta a[v]$ 和 Delta $b[v]$，详见代码。
AC代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> P; #define mk(x,y) make_pair(x,y) const ll mod=998244353; const int maxn=2e5+5; int n,m; int par[maxn]; ll a[maxn],b[maxn]; int find(int x) { if(par[x]==x) return x; int rt=find(par[x]); if(par[x]!=rt) a[x]+=a[par[x]], b[x]+=b[par[x]]; return par[x]=rt; } ll fpow(ll a,int n) { ll res=1, base=a%mod; while(n) { if(n&1) res*=base, res%=mod; base*=base, base%=mod; n>>=1; } return res%mod; } inline ll inv(ll a){return fpow(a,mod-2);} ll calc(int a,int b) { ll _1_3=inv(3), _2_3=2*_1_3%mod; ll res=fpow(3,n); res*=fpow(_2_3,a), res%=mod; res*=fpow(_1_3,b), res%=mod; return res; } int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin>>n>>m; for(int i=1;i<=n;i++) par[i]=i, a[i]=0, b[i]=0; for(int i=1,t,x,y;i<=m;i++) { cin>>t; if(t==1) { cin>>x>>y; a[x]++, b[y]++; a[y]-=a[x], b[y]-=b[x]; par[y]=x; } if(t==2) { cin>>x; int rt=find(x); if(x==rt) cout<<calc(a[x],b[x])<<" "; else cout<<calc(a[rt]+a[x],b[rt]+b[x])<<" "; } } }
PS.可怜老师出的并查集好强，充满了教育意义QAQ。