自动搬运

查看原文

来自洛谷，原作者为

	loveJY 世皆纵横，唯我彳亍

搬运于2025-08-24 22:31:51，当前版本为作者最后更新于2021-06-23 11:10:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

建议重写题面

题意:

长度为 $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$ 步

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

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

代码

#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;
}