题解：P10374 [AHOI2024 初中组] 操作

ylch · 2024-05-19 21:08:52 · 题解

这道题其实乍一看有点麻烦：要支持区间修改，修改的不是定值，而是操作，同时这个操作区间居然还可能有嵌套？我的天哪。

那么，就很自然地想到可以开一个数组记录每个位置被操作了多少次，对于 o_1=1 的位置，它的 a_i 要加上 y_i \times d_i（d_i 是 i 点的操作次数）；对于 o_i=2 的位置，要把它操作的区间里每个点操作次数加一。

仔细读题，观察到 x_i \le y_i \le i-1 这一关键条件，也就是说，第 i 个位置的值只会受后面的位置影响。

发现要区间修改，可以用差分标记，又因为第 i 个位置的值只会受后面的位置影响，所以只要把差分倒着跑一遍即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
const int mod = 10007;

int a[maxn], c[maxn], o[maxn], x[maxn], y[maxn];
int d[maxn]; // 差分数组

// 封装成函数，更方便
void add(int &x, int y) // 引用传参，这样可以同步修改x
{
    x = ((x + y) % mod + mod) % mod; // 因为可能溅出负数，所以要这样写
}

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;

    for(int i = 1; i <= k; i ++){
        cin >> c[i];
        d[c[i]] ++, d[c[i] - 1] --; // 边输入边差分，注意倒着
    }
    for(int i = 1; i <= m; i ++){
        cin >> o[i] >> x[i] >> y[i];
    }

    // 倒着跑差分，执行每一次操作
    for(int i = m; i >= 1; i --){
        add(d[i], d[i + 1]); // 求i位置的操作次数
        if(o[i] == 1){ // 操作1，单点修改
            add(a[i], y[i] * d[i]); // 注意把操作的次数d[i]乘到操作数y[i]上
        }else{ // 操作2，区间修改
            d[y[i]] += d[i];
            d[x[i] - 1] -= d[i]; // 注意是倒着的差分
        }
    }

    for(int i = 1; i <= n; i ++) cout << a[i] << ' ';
    cout << "\n";
}

int main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}