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 步

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

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

代码


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