[模拟赛]nodgd的猜球游戏

问题描述

nodgd和p6pou在玩猜球游戏,nodgd首先准备了10个小球，小球的编号从0~9。首先nodgd把这10个球按照从左到右编号为0,1,2,3...9的顺序摆在了桌子上，接下来nodgd把这10个球用10个不透明的杯子倒扣住。

nodgd接下来会按照一定的操作顺序以极快的速度交换这些杯子。
换完以后他问p6pou你看清楚从左到右的杯子中小球的编号了么？
由于p6pou的动态视力不是很好，所以她跑来向你求助。你在调查后发现nodgd置换杯子其实是有一定原则的。

具体来讲，nodgd有一个长度大小为n的操作序列。

操作序列的每一行表示一次操作都有两个非负整数a,b，表示本次操作将会交换从左往右数第a个杯子和从左往右数第b个杯子（a和b均从0开始数）。请注意是换杯子，而不是直接交换a号球和b号球。

nodgd和p6pou一共玩了m次猜球游戏，在每一轮游戏开始时，他都将杯子中的小球重置到从左往右依次为0,1,2,3...9的状态。

然后在第i轮游戏中nodgd会按照操作序列中的第个操作开始做，一直做到第个操作结束（和的编号从1开始计算）。

由于你提前搞到了nodgd的操作序列以及每一次游戏的l,r。请你帮助p6pou回答出nodgd每一轮游戏结束时，从左至右的杯子中小球的编号各是多少。

数据范围：\(1 \leq n,m \leq 10^5,0 \leq a,b \leq 9 ,1 \leq l\leq r \leq n\)

题解：

简而言之，本题给出了一个原序列和操作序列，操作为交换两个数的位置，询问执行\(l\)到\(r\)的操作后的结果。

我们考虑到执行同一操作后改变的只是其中两个值，可以考虑前缀和的思路，记录执行从1到r的结果，再通过结果数组求出1到\(l - 1\)的逆元操作，设\(k[i]\)表示\(l - 1\)次操作的第\(i\)项移动的位置，那么只需将第\(r\)次操作的序列移动到k[i]即可，所以答案为\(k[当前位r次操作的位置]\)

Code:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 5;
#define R register
typedef long long ll;
int a[MAXN],f[MAXN][15],k[MAXN];
int main()
{
    int n,m;
	scanf("%d %d", &n, &m);
	for(R int i = 0;i <= 9; i++)
		f[0][i] = i;
	for(R int i = 1;i <= n; i++)
	{
		int x,y;
		scanf("%d %d", &x, &y);
		for(R int j = 0;j <= 9; j++)f[i][j] = f[i - 1][j];
		swap(f[i][x],f[i][y]);
	}
	for(R int i = 1;i <= m; i++)
	{
		int l,r;
		scanf("%d %d", &l, &r);
		for(R int j = 0;j <= 9; j++)k[f[l - 1][j]] = j;
		for(R int j = 0;j < 9; j++)printf("%d ", k[f[r][j]]);
		printf("%d\n",k[f[r][9]]);
	}
    return 0;
}