题解：AT_abc425_c [ABC425C] Rotate and Sum Query

我们发现 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：

CPP

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

题解：AT_abc425_c [ABC425C] Rotate and Sum Query

文章操作

相关推荐

评论

题解：AT_abc425_c [ABC425C] Rotate and Sum Query