筱玛爱线段树

筱玛爱线段树

思路

比较容易想到离线后从后向前处理，所以我们只要维护两个差分数组即可了，
一个是答案数组，从前向后的，
一个是当编号被操作了几次的数组，从后向前的，
然后只需要按照要求模拟即可。

代码

/*
  Author : lifehappy
*/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, mod = 1e9 + 7;

ll op[N], l[N], r[N], ans[N], res[N], n, m;

int main() {
  // freopen("in.txt", "r", stdin);
  // freopen("out.txt", "w", stdout);
  // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  scanf("%d %d", &n, &m);
  for(int i = 1; i <= m; i++) {
    scanf("%d %d %d", &op[i], &l[i], &r[i]);
  }
  for(int i = m; i >= 1; i--) {
    res[i] = (res[i] + res[i + 1]) % mod;
    if(op[i] == 1) {
      ans[l[i]] = (ans[l[i]] + res[i] + 1) % mod;
      ans[r[i] + 1] = (ans[r[i] + 1] - res[i] - 1 + mod) % mod;
    }
    else {
      res[l[i] - 1] = (res[l[i] - 1] - res[i] - 1 + mod) % mod;
      res[r[i]] = (res[r[i]] + res[i] + 1) % mod;
    }
  }
  int key = 0;
  for(int i = 1; i <= n; i++) {
    key = (key + ans[i] + mod) % mod;
    printf("%d%c", key, i == n ? '\n' : ' ');
  }
    return 0;
}