分块 + 斜率优化

G真的比F2清真

首先,看到树上 + 子树操作,第一反应使用dfs序拍平。

那么这个问题就变成了支持:

  • 区间$a_i += x$
  • 询问区间$\max{|a_i| * |b_i|}$

考虑这个问题如何解决。

发现$b_i$并不会改变,所以预处理出来$|b_i|$。

之后考虑如何支持修改$a$,考虑斜率优化。

对于每个点维护$y = b_ix + a_i * b_i$的直线;

其中$x$表示的是这个点的$\Delta a_i$。

但是我们每次询问和修改的都是区间。

那么考虑分块,对于每个块内维护对应的凸壳。

然后对于每次修改,暴力重构边缘所在的块,对于中间完整覆盖的块,我们只需要打一个标记,代表这个块内所有东西的$a_i$值都加上了一个值,这样一来对于每块内他的$\Delta$就是一个相等的值,那么查询的时候边缘暴力做,中间可以在凸壳上二分。

那么还有一个问题:这个绝对值还没有解决。

$b_i$的问题非常好解决,预处理的时候取一下即可。

对于$a_i$这是一个取$\max$的问题,所以如果绝对值取反是肯定不优。那么只需要维护两个凸壳分别维护$a_i$取反和不取反的情况即可。

最终复杂度$O(n \sqrt{n} \log n)$,可能需要一些高超的卡常技巧,这边给一些卡常的技巧好了。

  • 块大小开小一点(这是最重要的一点),虽然询问时候复杂度是$O(\frac{n}{size} * \log{size})$,然后修改的时候暴力重构是$O(size * \log size)$的,但是询问的时候那个$\log$严重跑不满,暴力重构的$\log$是排序的,还是比较满的。
  • 维护凸壳的时候用$vector$,不要用数组(我也不知道为什么,反正这样变快了,$\color{black}{z} \color{red}{xyhh}$大爷说这是高速缓存的问题)。

最后上一波代码吧…

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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include<bits/stdc++.h>

#define SIZE 250
#define ll long long
#define INF 2147483647
#define is_bad(a, m, c) ((m.b - c.b) * (m.k - a.k) <= (a.b - m.b) * (c.k - m.k))

int inp(){
char c = getchar();
int neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
neg = -1;
c = getchar();
}
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum * neg;
}

int head[200010], nxt[200010], end[200010], dfn[200010], size[200010];
ll a2[200010], b2[200010], a[200010], b[200010];

int cou = 0;
void link(int a, int b){
nxt[++cou] = head[a];
head[a] = cou;
end[cou] = b;
}

struct Node{
ll k;
ll b;

ll get(int x){
return x * k + b;
}
};

bool cmp(Node a, Node b){
return a.k < b.k;
}

struct Convex{
std::vector<Node> s;

void insert(Node x){
while(s.size() > 1 && is_bad(s[s.size() - 2], s[s.size() - 1], x))
s.resize(s.size() - 1);
s.push_back(x);
}

ll query(ll x){
if(s.size() == 0)
return -1e18;
int l = 0;
int r = s.size() - 1;
while(l < r){
int mid = (l + r) >> 1;
if(s[mid].get(x) <= s[mid + 1].get(x))
l = mid + 1;
else
r = mid;
}
return s[l].get(x);
}

void clear(){
s.clear();
}
}c[1000], cf[1000];

int ql[1000], qr[1000];
ll delta[1000];
std::vector<Node> vec;

void rebuild(int x){
vec.clear();
c[x].clear();
cf[x].clear();
for(int i = ql[x]; i <= qr[x]; i++){
a[i] += delta[x];
vec.push_back((Node){b[i], a[i] * b[i]});
}
std::sort(vec.begin(), vec.end(), cmp);
for(int i = 0; i < vec.size(); i++)
c[x].insert(vec[i]);
for(int i = 0; i < vec.size(); i++)
cf[x].insert((Node){vec[i].k, -vec[i].b});
delta[x] = 0;
}

int idx = 0;
void dfs(int cur){
dfn[cur] = ++idx;
size[cur] = 1;
for(int x = head[cur]; x != -1; x = nxt[x]){
a[end[x]] += a[cur];
b[end[x]] += b[cur];
dfs(end[x]);
size[cur] += size[end[x]];
}
}

int main(){
memset(head, -1, sizeof(head));
int n = inp();
int q = inp();
for(int i = 2; i <= n; i++){
int fa = inp();
link(fa, i);
}
for(int i = 1; i <= n; i++)
a[i] = inp();
for(int i = 1; i <= n; i++)
b[i] = inp();
dfs(1);
memcpy(a2, a, sizeof(a));
memcpy(b2, b, sizeof(b));
for(int i = 1; i <= n; i++){
a[dfn[i]] = a2[i];
b[dfn[i]] = abs(b2[i]);
}
qr[0] = 0;
int cur = 1;
while(qr[cur - 1] < n){
ql[cur] = qr[cur - 1] + 1;
qr[cur] = ql[cur] + SIZE - 1;
cur++;
}
qr[cur - 1] = n;
for(int i = 1; i < cur; i++)
rebuild(i);
while(q--){
int op = inp();
if(op == 1){
int v = inp();
ll x = inp();
int l = dfn[v];
int r = dfn[v] + size[v] - 1;
int lb = (l - 1) / SIZE + 1;
int rb = (r - 1) / SIZE + 1;
if(lb == rb){
for(int i = l; i <= r; i++)
a[i] += x;
rebuild(lb);
} else {
for(int i = lb + 1; i < rb; i++)
delta[i] += x;
for(int i = l; i <= qr[lb]; i++)
a[i] += x;
for(int i = ql[rb]; i <= r; i++)
a[i] += x;
rebuild(lb);
rebuild(rb);
}
} else {
int v = inp();
int l = dfn[v];
int r = dfn[v] + size[v] - 1;
int lb = (l - 1) / SIZE + 1;
int rb = (r - 1) / SIZE + 1;
ll ans = -1e18;
if(lb == rb){
for(int i = l; i <= r; i++)
ans = std::max(ans, abs(a[i] + delta[lb]) * b[i]);
} else {
for(int i = lb + 1; i < rb; i++){
ans = std::max(ans, c[i].query(delta[i]));
ans = std::max(ans, cf[i].query(-delta[i]));
}
for(int i = l; i <= qr[lb]; i++)
ans = std::max(ans, abs(a[i] + delta[lb]) * b[i]);
for(int i = ql[rb]; i <= r; i++)
ans = std::max(ans, abs(a[i] + delta[rb]) * b[i]);
}
printf("%lld\n", ans);
}
}
}

 评论