DDOSvoid's Blog

Luogu U216697 线段树区间历史版本和

发表于 分类于
本文字数： 2.3k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/U216697

简要题意：给定一个长度为 $n$ 的序列 $a_i$，现在有 $m$ 次操作，操作有两种：给定区间 $[l,r]$ 和 $v$，将区间 $[l,r]$ 加上 $v$；给定区间 $[l,r]$，求区间 $[l,r]$ 的历史版本和

$n,m\le 10^5,a_i,v\le 1000$

Solution

首先明确我们需要用线段树维护区间和 $v$、区间历史和 $tv$，但是我们这里不引入时间的概念，我们将历史和 $tv$ 看成是 $v$ 乘上另一个标记 $t$，而每段时间，我们手动更新 $t$

即我们用线段树维护区间和 $v$、区间历史和 $tv$、标记 $t$、区间加标记 $add$、区间历史和加标记 $tadd$

首先我们认为 $t$ 标记优先级高于加标记，然后我们明确答案的形式

1
T[i].tv += t * T[i].v + tadd * (r - l + 1);

考虑 $t$ 对加法标记的影响，容易得到

1
T[i].tadd += t * T[i].add + tadd;

剩下的转移较为简单，不再赘述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#define maxn 100010
#define ll long long
using namespace std;

int n, m, a[maxn];

#define lc i << 1
#define rc i << 1 | 1 
struct Seg {
    ll v, tv;
    ll add, tadd, t;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].v = T[lc].v + T[rc].v;
    T[i].tv = T[lc].tv + T[rc].tv;
}

void build(int i, int l, int r) {
    if (l == r) return T[i] = { a[l], a[l], 0, 0, 0 }, void();
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

inline void Update(int i, int l, int r, ll add, ll tadd, ll t) {
    T[i].tv += t * T[i].v + tadd * (r - l + 1); 
    T[i].v += (r - l + 1) * add;
    T[i].tadd += t * T[i].add + tadd;
    T[i].t += t; 
    T[i].add += add;
}

inline void pushdown(int i, int l, int r) {
    ll &add = T[i].add, &tadd = T[i].tadd, &t = T[i].t, m = l + r >> 1;
    Update(lc, l, m, add, tadd, t); Update(rc, m + 1, r, add, tadd, t);
    add = tadd = t = 0; 
}

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, l, r, v, 0, 0);
    int m = l + r >> 1; pushdown(i, l, r);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
    maintain(i);
}

ll query(int i, int l, int r, int L, int R) {
    if (l > R || r < L) return 0;
    if (L <= l && r <= R) return T[i].tv;
    int m = l + r >> 1; pushdown(i, l, r);
    return query(lc, l, m, L, R) + query(rc, m + 1, r, L, R);
}

inline void solve_1() {
    int x, y, z; cin >> x >> y >> z;
    update(1, 1, n, x, y, z);
}

inline void solve_2() {
    int x, y; cin >> x >> y;
    cout << query(1, 1, n, x, y) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2();
        Update(1, 1, n, 0, 0, 1); 
    } 
    return 0;
}