P8165 [eJOI 2021] AddK 题解

zifuneko · 2026-06-09 12:31:54 · 题解

极小（K\le10）的区间修改以及区间查询，考虑树状数组。

• 对于极小的区间修改，可以考虑直接进行多次的单点修改。

• 对于区间查询，看图可以发现每个点的贡献是有规律的。

可以说是分为三个部分，左边是斜率一致的上坡，中间平坦，右边是斜率一致的下坡。那么答案可以写为

中间的平坦部分使用树状数组 S 维护 \sum A_i 即可；两边的坡由于斜率一致且为 45\degree，可以考虑再使用一个树状数组 T 维护 \sum i\cdot A_i 计算。记

上式等价于

时间复杂度为 O(QK\log N)。

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

const int MAX = 1e5 + 5;
int N, K, A[MAX], S[MAX], T[MAX];
int lowbit(int x) { return x & (-x); }
void add(int *t, int u, int x) { for(int i = u; i <= N; i += lowbit(i)) t[i] += x; }
int sum(int *t, int u) { int tol = 0; for(int i = u; i; i -= lowbit(i)) tol += t[i]; return tol; }
int sum(int *t, int l, int r) { return sum(t, r) - sum(t, l - 1); }

signed main()
{
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        cin >> A[i];
        add(S, i, A[i]);
        add(T, i, i * A[i]);
    }
    int Q; cin >> Q;
    while(Q--) {
        int opt; cin >> opt;
        if(opt == 1) {
            vector<int> pos(K), old(K);
            for(int i = 0; i < K; i++) cin >> pos[i], old[i] = A[pos[i]];
            for(int i = 0; i < K; i++) {
                int delta = old[(i + 1) % K] - old[i];
                add(S, pos[i], delta);
                add(T, pos[i], delta * pos[i]);
                A[pos[i]] = old[(i + 1) % K];
            }
        } else {
            int l, r, m; cin >> l >> r >> m;
            int ans = (m * sum(S, l, r))
                    + (sum(T, l, l + m - 1) - (l + m - 1) * sum(S, l, l + m - 1))
                    + ((r - m + 1) * sum(S, r - m + 1, r) - sum(T, r - m + 1, r));
            cout << ans << endl;
        }
    }
    return 0;
}