题目描述
牛牛拿到了一个长度为N的排列和M个区间，一开始排列是1、2、3…N。
然后他将这些区间在按顺序在排列上翻转，全部翻转一遍称一次操作。
现在他要去搞文化了…所以拜托你告诉他经过K次操作后的排列长什么样子。
输入描述:
第一行三个整数：N，M，K。
接下来M行，每行两个整数L和R描述一个区间。
输出描述:
输出一行N个数，表示经过K次操作后的排列。
示例1
输入
复制
5 2 2
1 4
2 3
输出
复制
1 2 3 4 5
说明
排列1 2 3 4 5中，区间[1 , 4]和[2 , 3]翻转后，排列为4 2 3 1 5。
再操作一次，则为1 2 3 4 5。
备注:
对于20%的数据，N <= 1e3，K <= 1e3
对于另外20%的数据，N <= 100，K <= 1e9
对于100%的数据，N <= 1e5，M <= 10，K <= 1e9，1 <= L <= R <= N
思路：
很明显就是将一个排列置换成另一个排列。
可以用并查集算出环中的真实节点，然后在将其在环中位置加k取模就知道下一个对应的位置。这是置换的一般方法。
或者也可以用倍增的方法，定义 f [ i ] [ j ] f[i][j] f[i][j]为 i i i置换 2 j 2^j 2j次后的数，那么只需要二进制拆解k就知道 i i i会被置换成什么数了。
置换的方法，枚举环中真实节点
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <iostream>
#include <vector>using namespace std;typedef unsigned long long ull;
const ull mod = 131;
const int maxn = 1e5 + 7;int p[maxn],fa[maxn],cnt[maxn],vis[maxn];
pair<int,int>a[maxn];
vector<int>G[maxn]; //环中节点int findset(int x) {if(fa[x] == x) return x;return fa[x] = findset(fa[x]);
}void Union(int x,int y) {int rx = findset(x),ry = findset(y);if(rx != ry) {fa[rx] = ry;}
}int main() {int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i = 1;i <= n;i++) {fa[i] = p[i] = i;}for(int i = 1;i <= m;i++) {scanf("%d%d",&a[i].first,&a[i].second);reverse(p + a[i].first,p + a[i].second + 1);}for(int i = 1;i <= n;i++) {Union(i,p[i]);}for(int i = 1;i <= n;i++) {cnt[findset(i)]++;}for(int i = 1;i <= n;i++) {if(!cnt[i]) continue;int now = i;for(int j = 0;j < cnt[i];j++) {vis[now] = j; //now在环中下标G[i].push_back(now);now = p[now];}}for(int i = 1;i <= n;i++) { //每个数映射成了什么int num = findset(i);int pos = vis[i];int len = cnt[num];p[i] = G[num][(pos + k) % len];}for(int i = 1;i <= n;i++) {printf("%d ",p[i]);}return 0;
}倍增做法
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
using namespace std;typedef long long ll;
const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;int to[maxn],f[maxn][33];int main() {int n,m,k;scanf("%d%d%d",&n,&m,&k);for(int i = 1;i <= n;i++) to[i] = i;for(int i = 1;i <= m;i++) {int x,y;scanf("%d%d",&x,&y);reverse(to + x,to + 1 + y);}for(int i = 1;i <= n;i++) f[i][0] = to[i];for(int j = 1;j <= 30;j++) {for(int i = 1;i <= n;i++) {f[i][j] = f[f[i][j - 1]][j - 1];}}for(int i = 1;i <= n;i++) {int now = i;for(int j = 30;j >= 0;j--) {if(k & (1 << j)) {now = f[now][j];}}printf("%d ",now);}return 0;
}