置换群 前缀和 思想

学好线性代数 做这题很有意思，记得多校也有一道置换群的好题～

把多次变换看成一个置换矩阵就好也就是

I (一开始为单位矩阵)  ->经过A作用产生了B->经过C作用产生了D

即  CAI = D

现在让我们求一下  CI  =？

两边右乘A的逆矩阵就好了～然后你再模拟一下就行了

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10;

vector<vector<int>>ball(N,vector<int>(15));



int n,m;

int tem[15];
int tem2[15];
int ans[15];
void inv(int x){
	for(int i=0;i<=9;i++){
		for(int j=0;j<=9;j++)
		 if(ball[x][j]==i)tem[i] = j;
	}
}

void print(int l,int r){
	
	inv(l-1); 
	for(int i=0;i<=9;i++)
	 tem2[i] = ball[r][i];
	
	for(int i=0;i<=9;i++)
	 ans[i] = tem[tem2[i]];
	
	//for(int i=0;i<=9;i++)cout<<tem[i]<<" \n"[i==9];
	//for(int i=0;i<=9;i++)cout<<ball[4][i]<<" \n"[i==9];
	
	for(int i=0;i<=9;i++)
	 cout<<ans[i]<<" \n"[i==9];
	
	
}
void solve()
{
	cin>>n>>m;
	
	for(int i=0;i<=9;i++)
	 ball[0][i] = i;
	
	for(int i=1;i<=n;i++){
		ball[i] = ball[i-1];
		int l,r;cin>>l>>r;
		swap(ball[i][l],ball[i][r]);
	}
	
	
	while(m--){
		int l,r;cin>>l>>r;
		print(l,r);
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;_ = 1;
	while(_--)solve();
}