筱玛爱线段树

这个看上去有点树套树的感觉,但是它的区间满足某些性质，于是可以差分做
首先有一个差分数组叫做 ，它的后缀和表示第 个操作被除了这个操作本身操作了多少次
还有一个 ，他的前缀和就表示第 的数的答案
然后题目的操作有一个性质：保证 小于当前操作的编号
所以是可以从后往前倒着推的，那么如果没有这个性质，那么就是可以用一个线段树什么的先维护每个操作操作了多少次，然后就是一个差分，差别不是很大吧

Code

#include <cstdio>

using namespace std;

const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

void print(int x)
{
    if (x / 10) print(x / 10);
    putchar(x % 10 + '0');
}

inline void add(int &x, int y)
{
    x += y - mod;
    x += (x >> 31) & mod;
}

int o[maxn], l[maxn], r[maxn];
int s[maxn], t[maxn];

int main()
{
    int n = __read(), m = __read();
    for (int i = 1; i <= m; ++i) 
        o[i] = __read(), l[i] = __read(), r[i] = __read();
    for (int i = m; i; --i) {
        add (s[i], s[i + 1]);
        if (o[i] == 1) add(t[l[i] - 1], mod - s[i] - 1), add(t[r[i]], s[i] + 1);
        else add(s[l[i] - 1], mod - s[i] - 1), add(s[r[i]], s[i] + 1);
        add ()
    }
    for (int i = 1; i <= n; ++i) {
        add(t[i], t[i - 1]);
        print (t[i]), putchar(' ');
    }
}