【每日一题】 筱玛爱线段树 题解

Description

筱玛是一个热爱线段树的好筱玛。
筱玛的爷爷马爷在游戏中被筱玛吊打了，于是他恼羞成怒，决定给筱玛出这样一道数据结构题：
给定一个长度为nn的数组AA，刚开始每一项的值均为00。
支持以下两种操作，操作共mm次

mm次操作结束后，你要告诉马爷AA数组变成什么样子了。
由于答案可能会很大，你只需要输出数组AA中的每个数在模意义下的值。

Solution

首先要知道差分是什么（其实我之前也不是很懂）
构造数组 那么
即 的前缀和
随后对于原数组 的区间修改可以通过差分实现
区间加1就是
这样区间[l, r]内的数字在通过前缀和计算的时候都是原来的数字+1，从而实现区间加的操作

有了这个前置知识，我们把原问题离线处理，从后往前做一个后缀和，判断当前是否是操作1还是操作2，用一个后缀和计算需要的次数即可，具体实现看代码，非常短，最后不要忘记取模。
时间复杂度

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const int mod = 1e9 + 7;
int l[N], r[N], op[N];
int sum[N], ans[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int n, T; cin >> n >> T;
  for(int i = 1; i <= T; i++) {
    cin >> op[i] >> l[i] >> r[i];
  }
  for(int i = T; i >= 1; i--) {
    sum[i] += sum[i + 1], sum[i] %= mod;
    if(op[i] == 1) { // 对原数组区间加
      ans[l[i]] += (1 + sum[i]), ans[l[i]] %= mod;
      ans[r[i] + 1] -= (1 + sum[i]), ans[r[i] + 1] = (ans[r[i] + 1] + mod) % mod;
    } else { // 操作2，对操作次数区间加
      sum[l[i] - 1] -= (sum[i] + 1), sum[l[i] - 1] = (sum[l[i] - 1] + mod) % mod;
      sum[r[i]] += (sum[i] + 1), sum[r[i]] %= mod;
    }
  }
  int now = 0;
  for(int i = 1; i <= n; i++) {
    now += ans[i]; // 前缀和就是原数组
    now %= mod;
    cout << now << " \n"[i == n];
  }
  return 0;
}