2020年論文題，這裡給出了一個（或許是）$o(n\log n+m\log^{2}n)$的做法，例題3即為原題
1.例題1
題面
給定$n$個一次函數$f_{i}(x)$，$m$次查詢$F(x)=\max_{i=1}^{n}f_{i}(x)$，強制線上
$1\le n,m\le 3\times 10^{5}$，$\left|[x^{j}]f_{i}(x)\right|,\left|x\right|\le 10^{9}$
DS序列
（以下序列被稱為Davenport-Schinzel序列，簡稱DS序列）
定義序列$\{\sigma_{1},\sigma_{2},...,\sigma_{m}\}$是$DS(n,s)$序列，當且僅當滿足以下條件：
1.$\forall 1\le i\le m,\sigma_{i}$是不超過$n$的正整數
2.$\{\sigma_{i}\}$中相鄰兩數不同（即$\forall 1\le i<m,\sigma_{i}\ne \sigma_{i+1}$）
3.$\{\sigma_{i}\}$不存在長度大于$s+1$的子序列，使得其是由兩個不同的元素交替構成
引理1：記$\lambda_{s}(n)$為最長的$DS(n,s)$序列長度，則有
$$
\lambda_{s}(n)=\begin{cases}n&(s=1)\\2n-1&(s=2)\\2n\alpha(n)+O(n)&(s=3)\\\Theta(n2^{\alpha(n)})&(s=4)\\\Theta(n\alpha(n)2^{\alpha(n)})&(s=5)\\n2^{\frac{\alpha(n)^{t}}{t!}+O(\alpha(n)^{t-1})}&(s\ge 6)\end{cases}
（其中$t=\lfloor\frac{s-2}{2}\rfloor$）
題解
稱兩個函數$f(x)$和$g(x)$是$s$階交替的，當且僅當$P(x)=[f(x)\le g(x)]$是不超過$s+1$段的分段常函數（顯然每一段均為0或1，也即大小關系至多變化$s$次）
進一步的，如果可以$o(s)$求出$P(x)$的分段情況，則稱兩者是可線性合并的
注意到一次函數兩兩一階交替，那麼記$G(x)=\min_{1\le i\le n,F(x)=f_{i}(x)}i$，顯然$G(x)$是一個分段常函數，将其中的常數取出構成一個序列，不難得到這是一個$DS(n,1)$序列
進而分治求出$G(x)$，又因為其可線性合并，預處理複雜度即$o(\lambda_{1}(n)\log n)=o(n\log n)$
每一次查詢二分即可，查詢複雜度即$o(m\log n)$
最終，總複雜度為$o(n\log n+m\log n)$，可以通過
拓展
在原問題的基礎上，考慮函數線上加入如何處理：
維護一個類似于動态開點線段樹的結構，但在區間内線段還不滿時不進行合并，顯然其均攤複雜度即與分治的複雜度相同，仍為$o(n\log n)$
考慮查詢，即需要對$o(\log n)$個部分分别二分，這樣的複雜度會變為$o(m\log^{2}n)$
考慮分散層疊算法，參考[luogu6466]（注意這裡要從高到低合并），那麼複雜度與修改複雜度相同，均攤後同樣是$o(n\log n)$的，同時查詢複雜度降為$o(m\log n)$
應用
（對于拓展問題）當函數有界限時（即線段），可以用李超線段樹$o(n\log^{2}n+m\log n)$實作
而借助此做法，将線段外的部分用$y=-\infty$補全，注意到這些函數兩兩3階交替且可線性合并，套用上述算法時間複雜度即$o(n\alpha(n)\log n+m\log n)$，略優于李超線段樹
2.例題2
給定$n$個一次函數$f_{i}(x)$，$m$次操作，支援：
1.修改$f_{i}(x)$（仍是一次函數）
2.查詢$F(x)=\max_{i=1}^{n}f_{i}(x)$，保證$x$單調不下降
強制線上
$1\le n,m\le 10^{5}$，$\left|[x^{j}]f_{i}(x)\right|,\left|x\right|\le 10^{9}$
（以下為了描述複雜度，均用$m_{i}$代指第$i$種操作的次數）
維護一棵線段樹，線段樹上每一個節點維護在區間内（對于目前的$x$）取到最大值的函數
當$x$增大時，一個節點被修改的必要條件為滿足以下兩者之一：1.其子樹内有節點被修改；2.其兩個兒子維護函數的大小關系發生了變化
由此，維護子樹中每一個節點兩個兒子下一次大小關系發生變化（相對于目前的$x$）的位置最小值，遞歸時若更改的$x$沒有達到該值即可直接退出
而大小關系發生變化實際上與之前的一階交替是相似的，是以每一個節點被直接修改（即滿足第2個條件）的次數為區間長度，進而會使得其到根路徑上$o(\log n)$個節點都被通路
考慮每一個節點的貢獻，不難發現即為$o(\log^{2}n)$，最終總均攤複雜度為$o(n\log^{2}n)$
修改以通常線段樹的形式實作即可，實際複雜度為$o(\log n)$
而對于均攤的複雜度，可以看作在該葉子上額外增加一個函數，同樣貢獻為$o(\log^{2}n)$
最終，總複雜度為$o(n\log^{2}n+m_{1}\log^{2}n+m_{2})$，可以通過
3.例題3
給定一棵$n$個點的樹，每一個點有點權$a_{i}$和$b_{i}$
記$R(v)$為$v$所有祖先（包括$v$）構成的集合，則$w_{v}=\left|\sum_{u\in R(v)}a_{u}\right|\left|\sum_{u\in R(v)}b_{u}\right|$
$m$次操作，支援：
1.給定$u$和$x$，将$a_{u}$增加$x$
2.給定$u$，查詢$u$子樹中（包括$u$）所有節點$w_{v}$的最大值
$1\le n\le 2\times 10^{5}$，$1\le m\le 10^{5}$，$1\le u\le n$，$0\le \left|a_{i}\right|,\left|b_{i}\right|,x\le 5\times 10^{3}$
注意到$w_{v}=\max(\sum_{u\in R(v)}b_{u}\sum_{u\in R(v)}a_{u},-\sum_{u\in R(v)}b_{u}\sum_{u\in R(v)})$，由于最終也是要取$\max$，不妨僅考慮前一項（兩項處理方式類似，分别求出後再取$\max$即可）
記$k_{v}=\sum_{u\in R(v)}b_{u}$，$w_{v}$的初值為$k_{v}\sum_{u\in R(v)}a_{u}$，建立dfs序後即需要支援：
1.給定$l,r$和$x$（其中$x\ge 0$），令$\forall l\le i\le r,w_{i}=k_{i}x+w_{i}$
2.給定$l$和$r$，查詢$\max_{l\le v\le r}w_{v}$
第一個操作似乎比較複雜，但實際上可以看作例題2中$x$區間增加（原來是全局增加），那麼即可類似地模仿例題2（當然實作上差別還是較大的），具體做法如下——
線上段樹上，維護目前在區間内（對于各自的$x$）取到最大值的函數和該子樹内$x$要增加多少才能使某個節點兩個兒子維護函數大小關系發生變化（由于$x$不同，這裡的定義要變為相對位置）
實作時，可以将修改的$x$直接乘上$k$加到$b$中，即變為關于$x$變化量的函數
這個問題的複雜度并不能簡單的描述，需要使用勢能分析——
注：這裡需要用到一次函數的性質，而不再僅僅是一階交替和可線性合并
定義一個節點"不平衡"當且僅當其兩個兒子中維護函數中的較大者斜率嚴格小于另一者，再定義其勢能為所有不平衡節點的深度和
勢能的範圍為$[0,n\log n]$，也即初始和結束的勢能差至多為$o(n\log n)$
對于修改，提取出所有被通路過的節點（不包括最後打标記的節點）得到一棵新樹
對于這棵新樹，去掉必然被通路的節點（即不被修改區間包含的區間），注意到這類點僅有$o(\log n)$個，也即最多會使勢能增加$o(\log^{2}n)$
對于剩下的新樹，考慮其中勢能的變化：
對于其中的葉子，其必然從平衡變為不平衡（根據結束條件顯然）
另一方面，注意到這些區間都被完全覆寫，不難證明每一個節點上維護函數的斜率和值均單調不下降，進而對于其中僅有一個兒子的節點，其不會從不平衡變為平衡
換言之，減少的勢能至少為所有葉子深度和，增加的勢能至多為所有有兩個兒子的節點深度和
對其再進行分析，考慮每一個節點的貢獻，即其子樹内葉子數-有兩個兒子的節點數，根據二叉樹的性質即為1，也即（這部分）均攤複雜度為$o(1)$
綜上，（單次）修改均攤複雜度為$o(\log^{2}n)$
另外，顯然（單次）查詢均攤複雜度為$o(\log n)$
最終，總複雜度為$o(n\log n+m_{1}\log ^{2}n+m_{2}\log n)$，可以通過
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 200005
4 #define ll long long
5 #define L (k<<1)
6 #define R (L+1)
7 #define mid (l+r>>1)
8 vector<int>v[N];
9 int n,m,p,x,y,a[N],b[N],dfn[N],sz[N],tag[N<<2];
10 struct Seg{
11 int tag[N<<2],mn[N<<2];
12 struct Line{
13 int k;
14 ll b;
15 }f[N<<2];
16 double get_point(Line x,Line y){
17 if (x.k==y.k)return 0x3f3f3f3f;
18 return -1.0*(x.b-y.b)/(x.k-y.k);
19 }
20 void upd(int k,int x){
21 tag[k]+=x,mn[k]-=x;
22 f[k].b+=(ll)x*f[k].k;
23 }
24 void up(int k){
25 double s=get_point(f[L],f[R]);
26 if (s<0)s=0x3f3f3f3f;
27 s=min(s,(double)0x3f3f3f3f);
28 mn[k]=min(min(mn[L],mn[R]),(int)floor(s));
29 if (f[L].b>f[R].b)f[k]=f[L];
30 else f[k]=f[R];
31 }
32 void down(int k){
33 upd(L,tag[k]);
34 upd(R,tag[k]);
35 tag[k]=0;
36 }
37 void init(int k,int l,int r,int x,Line y){
38 if (l==r){
39 f[k]=y;
40 return;
41 }
42 if (x<=mid)init(L,l,mid,x,y);
43 else init(R,mid+1,r,x,y);
44 }
45 void build(int k,int l,int r){
46 tag[k]=0;
47 if (l==r){
48 mn[k]=0x3f3f3f3f;
49 return;
50 }
51 build(L,l,mid);
52 build(R,mid+1,r);
53 up(k);
54 }
55 void update(int k,int l,int r,int x,int y,int z){
56 if ((l>y)||(x>r))return;
57 if ((x<=l)&&(r<=y)&&(mn[k]>=z)){
58 upd(k,z);
59 return;
60 }
61 down(k);
62 update(L,l,mid,x,y,z);
63 update(R,mid+1,r,x,y,z);
64 up(k);
65 }
66 ll query(int k,int l,int r,int x,int y){
67 if ((l>y)||(x>r))return -1e18;
68 if ((x<=l)&&(r<=y))return f[k].b;
69 down(k);
70 return max(query(L,l,mid,x,y),query(R,mid+1,r,x,y));
71 }
72 }T0,T1;
73 void dfs(int k,int sa,int sb){
74 dfn[k]=++dfn[0],sz[k]=1;
75 sa+=a[k],sb+=b[k];
76 T0.init(1,1,n,dfn[k],Seg::Line{sb,(ll)sa*sb});
77 T1.init(1,1,n,dfn[k],Seg::Line{-sb,-(ll)sa*sb});
78 for(int i=0;i<v[k].size();i++){
79 dfs(v[k][i],sa,sb);
80 sz[k]+=sz[v[k][i]];
81 }
82 }
83 int main(){
84 scanf("%d%d",&n,&m);
85 for(int i=2;i<=n;i++){
86 scanf("%d",&x);
87 v[x].push_back(i);
88 }
89 for(int i=1;i<=n;i++)scanf("%d",&a[i]);
90 for(int i=1;i<=n;i++)scanf("%d",&b[i]);
91 dfs(1,0,0);
92 T0.build(1,1,n),T1.build(1,1,n);
93 for(int i=1;i<=m;i++){
94 scanf("%d%d",&p,&x);
95 if (p==1){
96 scanf("%d",&y);
97 T0.update(1,1,n,dfn[x],dfn[x]+sz[x]-1,y);
98 T1.update(1,1,n,dfn[x],dfn[x]+sz[x]-1,y);
99 }
100 if (p==2)printf("%lld\n",max(T0.query(1,1,n,dfn[x],dfn[x]+sz[x]-1),T1.query(1,1,n,dfn[x],dfn[x]+sz[x]-1)));
101 }
102 return 0;
103 } View Code