题解：AT_abc425_c [ABC425C] Rotate and Sum Query

Claire0918 · 2025-09-29 15:43:29 · 题解

我们发现 1 操作实际上是进行长度为 c 的循环移位，而循环移位有以下性质：

两次循环移位可以合并，即做一次长度为 x 的后做一次长度为 y 的等同于做一次长度为 x + y 的。
循环移位的长度可以对 n 取模。
在移位长度为 x 的数组的 a'_i 等于原数组的 a_{(i + x - 1) \bmod n + 1}。

综上，记我们一共移位了 x 位，令 l' = (l + x - 1) \bmod n + 1, r' = (r + x - 1) \bmod n + 1，我们仅需要查询原数组中的

\begin{cases} \displaystyle \sum_{i \in [l', r']} a_i & l'\leq r'\\ \displaystyle \sum_{i \notin (r', l')} a_i & l' > r'\\ \end{cases}

即可。这可以直接使用前缀和维护，时间复杂度 \mathcal{O}(n + q)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10;

int n, q, sum = 0;
int a[maxn];
long long pre[maxn];

int main(){
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]), pre[i] = pre[i - 1] + a[i];
    }
    while (q--){
        int op, x, y;
        scanf("%d %d", &op, &x);
        if (op == 1){
            sum = (sum + x) % n;
        }else{
            scanf("%d", &y), x = (x + sum - 1) % n + 1, y = (y + sum - 1) % n + 1, printf("%lld\n", x <= y ? pre[y] - pre[x - 1] : pre[n] - pre[x - 1] + pre[y]);
        }
    }

return 0;
}