DDOSvoid's Blog

Luogu P5009 [yLOI2018] 不老梦

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

题目描述

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

唉，当年这道题的 $std$ 还是我写的，现在我却完全不会了

Solution

我们首先考虑如何记录答案

对于在 $t$ 时间对 $a$ 区间加 $add$，我们可以 $\sum v- t\cdot add\sum b$

然后在 $T$ 查询时输出 $\sum v + T\sum ab$，思想大概就是把 $a$ 和 $b$ 补齐到最新的 $a$ 和 $b$

然后我们发现我们需要维护的值有 $\sum v,\sum a,\sum b,\sum ab$

我们用分别用字母 $v,a,b,ab$ 来代替它们

然后我们考虑需要维护哪些标记

首先对于$a$ 区间加和 $b$ 区间加，我们肯定要维护 $adda$ 和 $addb$ 表示 $a$ 或 $b$ 区间加了多少

然后这两个标记对于维护 $ad$ 是普通关系标记，这个东西我们在 Luogu U140092 线段树练习 这道题里做过

然后我们考虑 $a$ 区间和 $b$ 区间加对 $v$ 的影响

我们发现这个东西相对于 $ad$ 的影响除了从正变成负以外还多了个 $t_i$

我们这就不用猜形式的方法了，我们采用另一种方法，手玩一下看看

能够得到 $v$ 应该减掉大概长得像这个东西 $Adda(b+addb)+Addb(a+adda)$，然后这个东西会按照 $update$ 的顺序来进行更新

另外为了方便我们把应该减掉的东西中的一部分放到标记 $addv$ 中，表示 $v$ 应该加多少

换句话说就是 $Adda,Addb$ 与 $adda,addb$ 是一组顺序关系变量，

具体的更新我就放到代码里了

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>
#include <cstdio>
#include <cctype>
#define gc getchar
#define maxn 200010
#define ll long long
#define cll const long long 
using namespace std;

int read() {
    int x = 0; bool f = 0; char c = gc();
    while (!isdigit(c)) { if (c == '-') f = 1; c = gc(); } 
    while (isdigit(c)) x = x * 10 + c - '0', c = gc();
    return f ? -x : x; 
} 

const int p = 100000007;

int n, m, a[maxn], v[maxn], b[maxn];

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    ll v, a, b, ab, adda, addb, addv, Adda, Addb;
} T[maxn * 4];
inline void maintain(int i) {
    T[i].v = (T[lc].v + T[rc].v) % p; 
    T[i].ab = (T[lc].ab + T[rc].ab) % p;
    T[i].a = (T[lc].a + T[rc].a) % p; 
    T[i].b = (T[lc].b + T[rc].b) % p; 
}

void build(int i, int l, int r) {
    if (l == r) {
        T[i].v = v[l]; T[i].ab = 1ll * a[l] * b[l] % p; 
        T[i].a = a[l]; T[i].b = b[l]; return ; 
    } 
    int m = l + r >> 1;
    build(lc, l, m); build(rc, m + 1, r);
    maintain(i);
}

void Update_v(int i, int l, int r, cll &adda, cll &addb, cll &addv, cll &Adda, cll &Addb) {
    T[i].v = (T[i].v - Adda * T[i].b - Addb * T[i].a + addv * (r - l + 1)) % p;
    T[i].ab = (T[i].ab + T[i].a * addb + T[i].b * adda + adda * addb % p * (r - l + 1)) % p;
    T[i].a = (T[i].a + adda * (r - l + 1)) % p;
    T[i].b = (T[i].b + addb * (r - l + 1)) % p; 
}

void Update_tag(int i, int l, int r, cll &adda, cll &addb, cll &addv, cll &Adda, cll &Addb) {
    T[i].addv = (T[i].addv + addv - T[i].adda * Addb - T[i].addb * Adda) % p;
    
    T[i].Adda = (T[i].Adda + Adda) % p;
    T[i].Addb = (T[i].Addb + Addb) % p; 
    T[i].adda = (T[i].adda + adda) % p;
    T[i].addb = (T[i].addb + addb) % p;   
} 

void pushdown(int i, int l, int r){
	ll &adda = T[i].adda, &addb = T[i].addb, &addv = T[i].addv; 
	ll &Adda = T[i].Adda, &Addb = T[i].Addb; int m = l + r >> 1;
    
    Update_v(lc, l, m, adda, addb, addv, Adda, Addb);
    Update_v(rc, m + 1, r, adda, addb, addv, Adda, Addb);

    Update_tag(lc, l, m, adda, addb, addv, Adda, Addb);
    Update_tag(rc, m + 1, r, adda, addb, addv, Adda, Addb);

    adda = addb = addv = Adda = Addb = 0; 
}

void update_adda(int i, int l, int r, int L, int R, ll v, ll t) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) {
        Update_v(i, l, r, v, 0, 0, v * t % p, 0);
        Update_tag(i, l, r, v, 0, 0, v * t % p, 0);
        return ;
    } 
    int m = l + r >> 1; pushdown(i, l, r);
    update_adda(lc, l, m, L, R, v, t); update_adda(rc, m + 1, r, L, R, v, t);
    maintain(i);
}

void update_addb(int i, int l, int r, int L, int R, ll v, ll t) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) {
        Update_v(i, l, r, 0, v, 0, 0, v * t % p);
        Update_tag(i, l, r, 0, v, 0, 0, v * t % p);
        return ;
    }
    int m = l + r >> 1; pushdown(i, l, r);
    update_addb(lc, l, m, L, R, v, t); update_addb(rc, m + 1, r, L, R, v, t);
    maintain(i);
}

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

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

inline void solve_1() {
    int t = read(), x = read(), y = read();
    printf("%d\n", (query(1, 1, n, x, y, t) + p) % p); 
}

inline void solve_2() {
    int t = read(), x = read(), y = read(), z = read();
    update_adda(1, 1, n, x, y, z, t); 
} 

inline void solve_3() {
    int t = read(), x = read(), y = read(), z = read();
    update_addb(1, 1, n, x, y, z, t); 
} 

inline void solve_4() {
    int t = read(), x = read(), y = read(), z = read();
    update_addv(1, 1, n, x, y, z); 
} 

int main() { 
    n = read(); m = read();
    for (int i = 1; i <= n; ++i) v[i] = read(), a[i] = read(), b[i] = read();
    build(1, 1, n); 
    for (int i = 1; i <= m; ++i) {
        int opt = read();
        switch (opt) {
        case 1 : solve_1(); break;
        case 2 : solve_2(); break;
        case 3 : solve_3(); break;
        case 4 : solve_4(); break;
        }
    }
    return 0; 
}