P7647 [COCI2012-2013#5] ROTIRAJ

建议重写题面

# 题意:

长度为 $N$ 的序列,从左向右每 $k$ 个位置切一刀分割成 $\frac{n}{k}$ 个区间,保证 $k|n$

第一类操作为每个子序列左/右移 $k$ 位

第二类操作为所有位置左/右移 $k$ 位

然后两类操作均为循环移位,即1234左移后变为2341

给出 $Q$ 次操作后的序列,求操作前的序列

$N,Q,k\leq 100000$
## Part1

观察到该操作具有可逆性,因此只需要把 $Q$ 次操作倒序回去左右颠倒后对于目标序列做一遍,得到的就是初始序列
## Part2

考虑根号分治,当 $k>\sqrt n$ 的时候我们可以对于枚举每一块并进行操作

显然不能直接循环移位,因此考虑维护块内真实的开头指针

整体左移则是上一块的开头会放入这一块的结尾,并且这一块的开头会消失,可以直接将上一块开头放入这一块开头并将指针移动,整体右移同理.

若 $k<\sqrt n$ ,我们需要维护 $\bmod k$ 同余的所有位置,不难发现他们之间的相邻数的相对距离不会发生改变,因此我们只需要记录每个 $\bmod k$ 同余的位置中第一块的开头到底是什么数即可,在整体左右移动的时候仍然需要改指针和这个数组的信息.

复杂度为 $O(q\sqrt n)$ ,但是只要下手写一下你就会发现一个线性做法
## Part3

考虑我们 $k\leq\sqrt n$ 的部分,对于他们的操作复杂度似乎仅仅在于一个```第一块开头```是什么数组的维护

而这个数组可以记录 $dis$ 表示第一块开头真实值是维护 $dis*k+a$ 位置

那么我们每次整体移动操作,就仅仅相当于对于 $dis$ 数组循环走过 $x_i$ 步(比如向右走,就是在走过结尾的时候自动跳到开头)并把经过的数都+1,然后把指针整体移动 $x_i$ 步

而这个过程显然可以用差分数组来优化!

因此本题也就做完了,对于二操作直接差分,一操作只是简单的循环位移而已

# 代码

```cpp

#include<bits/stdc++.h>
#define pb push_back
#define vi vector<int>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 7;
int n, k, q;
int typ[MAXN], x[MAXN], a[MAXN];
ll pos[MAXN];
vi b[MAXN];
inline void IO() {
	scanf("%d%d%d", &n, &k, &q);
	for(int i = 1; i <= q; ++i) {
		scanf("%d%d", &typ[i], &x[i]);
		x[i] = -x[i];
	}
	reverse(typ + 1, typ + q + 1);
	reverse(x + 1, x + q + 1);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		b[i % k].pb(a[i]);
	}
	return;
}

inline void solve1() {
	int hd = 0;
	for(int i = 1; i <= q; ++i) {
		if(typ[i] == 1) {
			hd = ((hd - x[i]) % k + k) % k;
		} else {
			if(x[i] < 0) {
				int q = -x[i];
				if(q <= k - hd) {
					pos[hd]++;
					pos[hd + q]--;
				} else {
					--q;
					pos[hd]++;
					q -= k - hd;
					if(q >= k) {
						pos[0] += q / k;
						q = q % k;
					}
					pos[0]++;
					pos[q + 1]--;
				}
			} else {
				int q = x[i];
				int tl = (hd - 1 + k) % k;
				if(q <= tl) {
					pos[tl - q + 1]--;
					pos[tl + 1]++;
				} else {
					--q;
					pos[0]--;
					pos[tl + 1]++;
					q -= tl;
					if(q >= k) {
						pos[0] -= q / k;
						q = q % k;
					}
					pos[k - q]--;
				}
			}
			hd = (hd - x[i] % k + k) % k;
		}
	}
	for(int i = 1; i < k; ++i)pos[i] += pos[i - 1];
	for(int i = 0; i < n; i += k) {
		for(int j = hd;; j = (j + 1) % k) {
			printf("%d ", b[j][(i / k + pos[j] % (n / k) + n / k) % (n / k)]);
			if((j + 1) % k == hd)break;
		}
	}
	puts("");
	return ;
}

int main() {
	IO();
	solve1();
	return 0;
}

```

正在渲染内容...