LG7442 「EZEC-7」维护序列

发布于 2021-03-26  1.39k 次阅读


题面

分析

显然每一次操作可以让位置为 $x$ 的数排到 $\frac x 2$ 或 $\frac x 2 + 2^{n-1}$ 的位置。

我们可以尝试将这样的操作理解为:在二进制意义下,我们把 $x$ 的最低位移到了最高位,并且有可能让该位反转。

尝试举几个例子可以发现,操作一在将最低位移到最高位时无需反转该位;而操作二则需反转该位。

记录所有操作带来的更改,最后从询问给出的 $x$ 反推回最初的位置即可。

具体实现方法见代码。

这个做法时间复杂度为 $O(nq)$,与部分题解做法相比可能较慢

代码

我们考虑记 rev[i] 表示记录第 $i$ 位是否需要反转。

下面的代码中记 $p$ 表示原坐标一共右移了几次(即操作了几次),$p=n$ 时令 $p=0$。

/**
 * @author Macesuted
 * @date 2021-03-20
 * 
 * @copyright Copyright (c) 2021
 * 
 */

#include <bits/stdc++.h>
using namespace std;

using io::getch;
using io::putch;
using io::read;
using io::write;

#define maxn 64

bool rev[maxn];
long long ln[maxn];

int main() {    
    register int n = read<int>(), m = read<int>(), p = 0;
    ln[0] = 1;
    for (register int i = 1; i < maxn; i++) ln[i] = ln[i - 1] << 1;
    while (m--)
        if (read<int>() == 1) {
            if (read<int>()) rev[p] ^= true; //如果是操作二则需反转最低位
            if (++p == n) p = 0; //右移了一位
        } else {
            register long long x = read<long long>();
            for (register int j = 0; j < p; j++) x = ((x << 1) & (ln[n] - 1)) | (x >> (n - 1) & 1); //将最高位移到最低位
            for (register int j = 0; j < n; j++)
                if (rev[j]) x ^= ln[j]; //反转部分位
            write(x), putch('\n');
        }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话