【题解】[洛谷 P5654] 基础函数练习题

比较有趣的题目。学到许多。

YSGH 有一个 $1 \sim n$ 的排列 $p$ 和一个长度为 $n$ 的整数序列 $w$。
定义:

其中 $m$ 为 $p$ 的区间 $[l, r]$ 的最大值的下标。

$q$ 次询问 $F(l, r)$ 的值。

$1\leq n,q \leq 5\times 10^5$ 。

大概是比较神的题?首先如果考虑是 $F(1,n)$,那么转移就是一个笛卡尔树的形式。然后如果放到区间里来,可以发现可能会存在从 $l$、$r$ 到根的链被修改,中间的链不会被改变。

而这个被修改成的模样大概是要稍微找一下性质。可以发现对于 $l$ 而言,首先他的左子树会被砍掉,其次考虑对笛卡尔树的父子关系分类,称 ${\rm Lson}(x)=y$ 的父子关系 $(y,x)$ ,其中 $x$ 是 $y$ 的右行父亲,${\rm Rson}(x)=y$ 的则为左行父亲。那么不难看出,对于 $l\to root$ 这条链上,任何一个键值(下标)比 $l$ 小的都需要被删掉,也就是所有右行父亲都要被删掉;同理对于 $r\to root$ 这条脸上,所有左行父亲需要被删掉。

发现询问可以离线,于是考虑拆成两半做。这个地方需要一个神奇的 Observation。观察 $F$ 在笛卡尔树上的展开式:

不难发现 $m_k$ 只会与对应节点有关,同时 $\max$ 有结合律,整个式子都被 $\max$ 包住了,于是就可以直接倍增。

具体的,考虑设 $g_{x,k}$ 表示 $x$ 的 $2^{k-1}$ 祖先的内向子树的贡献和,$f_{x,k}$ 表示从 $x$ 到 $x$ 的 $2^{k-1}$ 祖先的点权和,$fa_{x,k}$ 表示对一个固定的方向,即不考虑「左行」或者「右行」父亲时的父亲。那么预处理时 $f_{x,k}$ 较容易维护,考虑 $g_{x,k}$ ,发现倍增是需要考虑分成两个 $2^{k-1}$ 规模的子问题去计算,也就是此时需要分别计算 $2^{k-1}$ 级祖先上面的和下面的贡献,拼一下的话比较直观。

然后就可以考虑如何计算答案。发现由于上文提到过的结合律,可以发现只需要比较链上的答案和子树内的答案的 $\max$ 就好了。

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
#include <cstdio>

#include <vector>

#include <cstring>

#include <iostream>

using namespace std ;

typedef long long ll ;

const int N = 500005 ;

const ll I = 1ll << 50 ;

inline int rd(){
register int r = 0, f = 1 ;
register char c = getchar() ;
while (c > '9' || c < '0'){
if (c == '-') f = -1 ; c = getchar() ;
}
while (c <= '9' && c >= '0'){
r = (r << 1) + (r << 3) + c - '0', c = getchar() ;
}
return r * f ;
}

int n ;
int q ;
int rt ;
int tp ;

int p[N] ;
int w[N] ;
int ql[N] ;
int qr[N] ;
int qlca[N] ;

int lc[N] ;
int rc[N] ;
int dep[N] ;
int stk[N] ;

ll ans[N] ;
ll sum[N] ;
ll f[N][19] ;
ll g[N][19] ;
int fa[N][19] ;

void dfs(int x){
dep[x] = dep[fa[x][0]] + 1 ;
for (int i = 1 ; i < 19 ; ++ i){
if (!fa[x][i - 1]) break ;
fa[x][i] = fa[fa[x][i - 1]][i - 1] ;
}
if (lc[x]) dfs(lc[x]) ;
if (rc[x]) dfs(rc[x]) ;
sum[x] = max(sum[lc[x]], sum[rc[x]]) + w[x] ;
}
inline int lca(int x, int y){
int d = dep[x] - dep[y] ;
if (dep[x] < dep[y])
swap(x, y), d = -d ;
for (int i = 0 ; d ; ++ i, d >>= 1)
if (d & 1) x = fa[x][i] ;
if (x == y) return x ;
for (int i = 18 ; ~ i ; -- i)
if (fa[x][i] != fa[y][i])
x = fa[x][i], y = fa[y][i] ;
return fa[x][0] ;
}
void do_do(int x, int v){
register int o ;
register int p = lc[x] ;
register int q = rc[x] ;
f[x][0] = g[x][0] = w[x] ;
g[x][0] += v ? sum[p] : sum[q] ;
for (int i = 1, j ; i < 19 ; ++ i){
j = i - 1 ;
o = fa[x][j] ;
fa[x][i] = fa[o][j] ;
if (!fa[x][i]) break ;
f[x][i] = f[x][j] + f[o][j] ;
g[x][i] = max(g[o][j], g[x][j] + f[o][j]) ;
}
if (lc[x]) fa[lc[x]][0] = v ? fa[x][0] : x ;
if (rc[x]) fa[rc[x]][0] = v ? x : fa[x][0] ;
if (lc[x]) do_do(lc[x], v) ;
if (rc[x]) do_do(rc[x], v) ;
}
inline ll solve(int x, int y){
register ll ret = 0 ;
for (int i = 18 ; ~ i ; -- i)
if (dep[fa[x][i]] >= dep[y])
ret = max(ret + f[x][i], g[x][i]), x = fa[x][i] ;
return ret ;
}
int main(){
n = rd() ; q = rd() ;
p[stk[tp = 1] = 0] = n + 1 ;
for (int i = 1 ; i <= n ; ++ i) p[i] = rd() ;
for (int i = 1 ; i <= n ; ++ i) w[i] = rd() ;
for (int i = 1 ; i <= n ; ++ i){
while (tp && p[stk[tp]] < p[i]) -- tp ;
fa[i][0] = stk[tp] ; int z = rc[stk[tp]] ;
fa[z][0] = i ; lc[i] = z ; rc[fa[i][0]] = i ;
stk[++ tp] = i ;
}
dfs(rt = lc[0] + rc[0]) ;
for (int i = 1 ; i <= q ; ++ i){
ql[i] = rd() ; qr[i] = rd() ;
qlca[i] = lca(ql[i], qr[i]) ;
}
memset(fa, 0, sizeof fa) ; do_do(rt, 0) ;
for (int i = 1 ; i <= q ; ++ i)
ans[i] = w[qlca[i]] + solve(ql[i], qlca[i]) ;
memset(fa, 0, sizeof fa) ; do_do(rt, 1) ;
for (int i = 1 ; i <= q ; ++ i)
ans[i] = max(ans[i], w[qlca[i]] + solve(qr[i], qlca[i])) ;
for (int i = 1 ; i <= q ; ++ i)
printf("%lld\n", ans[i]) ; return 0 ;
}