YACS 2023年1月月赛 乙组 T4 加与乘（二） 题解

题目链接

应大家的要求，早上起来更一下乙组 T4。

这一道题目我们发现不仅会加元素了，还会重复执行任务。

很容易想到用两个树状数组来维护每个任务的执行次数，以及每个单元格中的数字。

逆向扫一下，轮到这个操作的时候先把这个操作执行次数算一下，

然后把这个操作的贡献做执行次数次就行了。

用指针写的话可以方便一点。

代码：

#include <iostream>
#define int long long
using namespace std;
int n, m;
int t1[200005], t2[200005];
int query (int t[], int x) {
    if (x == 0) return 0;
    return (t[x] + query (t, x - (x & -x) ) ) % 1000000007;
}
void add (int t[], int x, int y) {
    if (x > max(n, m) ) return;
    t[x] = (t[x] + y) % 1000000007;
    add (t, x + (x & -x), y);
}
struct Upd {
    char op;
    int l, r;
}a[200005];
signed main () {
    ios::sync_with_stdio (false);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) cin >> a[i].op >> a[i].l >> a[i].r;
    for (int i = m; i >= 1; i --) {
        int time = query (t2, i) + 1;
        if (a[i].op == '+') {
            add (t1, a[i].l, time);
            add (t1, a[i].r + 1, - time);
        }
        if (a[i].op == '*') {
            add (t2, a[i].l, time);
            add (t2, a[i].r + 1, -time);
        }
    }
    for (int i = 1; i <= n; i ++) cout << (query (t1, i) + 1000000007) % 1000000007 << "\n";
    return 0;
}