省选数据结构学习笔记
xtx1092515503
2021-02-10 15:28:32
这里是省选数据结构（中的一部分）的学习笔记。
有关线段树合并、区间取最值数据结构、李超线段树、CDQ分治、整体二分、可并堆的题（可能）可以在本博客中找到。
有关KDT、替罪羊树、历史最值数据结构、块状链表、莫队的题则（可能）可以在[省选学习笔记II](https://www.luogu.com.cn/blog/Troverld/Data-Structures-Return)中找到。其也是本作的续集。
大部分数据结构还附有入门讲解，~~加量不加价~~。
其余的省选数据结构（**常规**平衡树、树套树及**普通**线段树等）可以在[搞基数据结构学习笔记](https://www.luogu.com.cn/blog/Troverld/ping-heng-shu-shu-tao-shu-xue-xi-bi-ji)中找到。其是本作的姊妹篇。
# I.线段树合并
## I.I.[[POI2011]ROT-Tree Rotations](https://www.luogu.com.cn/problem/P3521)
可以发现，你无论如何交换某个节点里的儿子们，该节点子树内每个数的数量都是不变的。
于是我们考虑类CDQ分治的思想——先计算儿子内部最小逆序对数，然后再在父亲处计算两个儿子之间的最小逆序对数。
因为保证叶节点上的东西是排列，所以设左儿子的叶子数是 $L$，右儿子的叶子数是 $R$，则总对数即为 $L\times R$。若把左儿子放在前面时的逆序对数是 $I$，则右儿子在前的逆序对数即为 $LR-I$。于是现在仅需求出一个儿子在前时的逆序对数即可。
考虑线段树合并。在线段树合并左右儿子的权值线段树时，仍然可以再次使用类CDQ分治思想——先算出前一半区间内逆序对数，再算出后一半区间内逆序对数，最后计算跨区间逆序对数，发现就是 $[mid+1,r]_L\times[l,mid]_R$。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,rt[400100],ls[400100],rs[400100],tot,cnt,RT;
ll inv,res;
struct SegTree{
int lson,rson,sum;
}seg[10001000];
#define mid ((l+r)>>1)
void modify(int &x,int l,int r,int P){
if(l>P||r<P)return;
if(!x)x=++cnt;seg[x].sum++;
if(l!=r)modify(seg[x].lson,l,mid,P),modify(seg[x].rson,mid+1,r,P);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;
int z=++cnt;
if(l==r)seg[z].sum=seg[x].sum+seg[y].sum;
else seg[z].sum=seg[seg[z].lson=merge(seg[x].lson,seg[y].lson,l,mid)].sum+seg[seg[z].rson=merge(seg[x].rson,seg[y].rson,mid+1,r)].sum,inv+=1ll*seg[seg[x].rson].sum*seg[seg[y].lson].sum;
return z;
}
void dfs(int &x){
x=++tot;
int k;scanf("%d",&k);
if(k)modify(rt[x],1,n,k);
else dfs(ls[x]),dfs(rs[x]),inv=0,rt[x]=merge(rt[ls[x]],rt[rs[x]],1,n),res+=min(inv,1ll*seg[rt[ls[x]]].sum*seg[rt[rs[x]]].sum-inv);
}
int main(){
scanf("%d",&n),dfs(RT),printf("%lld\n",res);
return 0;
}
```
## I.II.[[ZJOI2019]语言](https://www.luogu.com.cn/problem/P5327)
~~一开始看错题，以为同一种语言会被普及多次，然后就成了神题不会做。一看题解，发现自己看错题了，原来是垃圾题。~~
一个点所能到达的点，只有与它在同一条路径上出现过的点，换句话说就是经过它全部路径的并。
全部路径的并很好搞，就是全部路径端点建出虚树的大小。虚树大小也很好搞，就是将所有点按dfs序排序后，两两相邻点（包括一头一尾）间距离之和的二分之一。
于是就要对每个点维护所有经过它的路径的端点。对于一条路径，其相当于是对经过的所有点的端点集合内多加了两个点，也即静态路径加，树上差分随手搞。
但是树上差分就意味着一个节点的端点集合是其所有儿子的端点集合之并。于是随手线段树合并维护一下即可。
需要注意的是，这样搞会使得一个点对被计算两遍，答案应该除以 $2$。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll res;
int n,m,dfn[100100],pa[100100],rev[100100],fir[100100],tot,lim,st[200100][20],LG[200100],dep[100100],rt[100100],cnt;
vector<int>v[100100];
void dfs(int x,int fa){
pa[x]=fa,dfn[x]=++tot,rev[tot]=x,st[++lim][0]=x,fir[x]=lim,dep[x]=dep[fa]+1;
for(auto y:v[x])if(y!=fa)dfs(y,x),st[++lim][0]=x;
}
int MIN(int x,int y){return dep[x]<dep[y]?x:y;}
int LCA(int x,int y){
x=fir[x],y=fir[y];
if(x>y)swap(x,y);
int k=LG[y-x+1];
return MIN(st[x][k],st[y-(1<<k)+1][k]);
}
int DIS(int x,int y){return dep[x]+dep[y]-2*dep[LCA(x,y)];}
#define mid ((l+r)>>1)
struct SegTree{
int lson,rson,lval,rval,sum,tms;
}seg[3201000];
void pushup(int &x){
if(!seg[x].lson&&!seg[x].rson){x=0;return;}
if(seg[x].lson&&!seg[x].rson){seg[x].lval=seg[seg[x].lson].lval,seg[x].rval=seg[seg[x].lson].rval,seg[x].sum=seg[seg[x].lson].sum;return;}
if(!seg[x].lson&&seg[x].rson){seg[x].lval=seg[seg[x].rson].lval,seg[x].rval=seg[seg[x].rson].rval,seg[x].sum=seg[seg[x].rson].sum;return;}
seg[x].lval=seg[seg[x].lson].lval,seg[x].rval=seg[seg[x].rson].rval;
seg[x].sum=seg[seg[x].lson].sum+seg[seg[x].rson].sum+DIS(seg[seg[x].lson].rval,seg[seg[x].rson].lval);
}
void turnon(int &x,int l,int r,int P){
if(l>P||r<P)return;
if(!x)x=++cnt;
if(l==r)seg[x].lval=seg[x].rval=rev[P],seg[x].tms++;
else turnon(seg[x].lson,l,mid,P),turnon(seg[x].rson,mid+1,r,P),pushup(x);
}
void turnoff(int &x,int l,int r,int P){
if(l>P||r<P||!x)return;
if(l==r){seg[x].tms--;if(!seg[x].tms)x=0;}
else turnoff(seg[x].lson,l,mid,P),turnoff(seg[x].rson,mid+1,r,P),pushup(x);
}
void merge(int &x,int y,int l,int r){
if(!x){x=y;return;}
if(!y)return;
if(l==r){seg[x].tms+=seg[y].tms;return;}
merge(seg[x].lson,seg[y].lson,l,mid),merge(seg[x].rson,seg[y].rson,mid+1,r),pushup(x);
}
vector<int>in[100100],out[100100];
void dfs2(int x,int fa){
for(auto y:v[x])if(y!=fa)dfs2(y,x),merge(rt[x],rt[y],1,n);
for(auto i:in[x])turnon(rt[x],1,n,i);
for(auto i:out[x])turnoff(rt[x],1,n,i);
res+=seg[rt[x]].sum+DIS(seg[rt[x]].lval,seg[rt[x]].rval);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs(1,0);
for(int i=2;i<=lim;i++)LG[i]=LG[i>>1]+1;
for(int j=1;j<=LG[lim];j++)for(int i=1;i+(1<<j)-1<=lim;i++)st[i][j]=MIN(st[i][j-1],st[i+(1<<(j-1))][j-1]);
for(int i=1,x,y;i<=m;i++){
scanf("%d%d",&x,&y);
in[x].push_back(dfn[x]),in[x].push_back(dfn[y]);
in[y].push_back(dfn[x]),in[y].push_back(dfn[y]);
int lca=LCA(x,y);
// printf("%d %d %d\n",x,y,lca);
out[lca].push_back(dfn[x]),out[lca].push_back(dfn[y]);
out[pa[lca]].push_back(dfn[x]),out[pa[lca]].push_back(dfn[y]);
}
dfs2(1,0),printf("%lld\n",res>>2);
return 0;
}
```
## I.III.[[PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298)
~~看错题+理解错题，成功自闭一整晚~~
首先，一上来我们就能想到，如果用一个数组来表示每个节点所有可能出现的值及其概率，就会比较轻松。而因为树上父节点的数组是由两个子节点的数组合在一起转移而来的，所以考虑用线段树合并来维护该数组。
显然，没有儿子时转移很轻松；仅有一个儿子时，因为儿子取值唯一，就直接继承儿子的即可；有两个儿子时，观察如果是左儿子上的值 $u$ 成功转移，则要么是所有右儿子的取值都比它大，且在取 $\min$；要么是所有右儿子的取值都比它小，且在取 $\max$；而这是前后缀和的形式。于是我们在线段树合并时维护一大坨前缀和后缀和一类然后就能轻松转移了。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int inv10k=796898467;
int n,rt[300100],p[300100],m,cnt,res;
vector<int>v[300100],u;
int ksm(int x,int y=mod-2){
int z=1;
for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)z=1ll*z*x%mod;
return z;
}
#define mid ((l+r)>>1)
struct SegTree{int lson,rson,sum,tag;}seg[10001000];
void modify(int &x,int l,int r,int P){
if(l>P||r<P)return;
if(!x)x=++cnt,seg[x].tag=1;(++seg[x].sum)%=mod;
// printf("%d %d %d %d\n",x,l,r,P);
if(l!=r)modify(seg[x].lson,l,mid,P),modify(seg[x].rson,mid+1,r,P);
}
void MUL(int x,int y){seg[x].sum=1ll*seg[x].sum*y%mod,seg[x].tag=1ll*seg[x].tag*y%mod;}
void pushdown(int x){MUL(seg[x].lson,seg[x].tag),MUL(seg[x].rson,seg[x].tag),seg[x].tag=1;}
int merge(int x,int y,int lamxl,int lamxr,int lamyl,int lamyr,int p){
// printf("(%d %d %d %d %d %d %d)\n",x,y,lamxl,lamxr,lamyl,lamyr,p);
if(x)pushdown(x);if(y)pushdown(y);
if(!x){MUL(y,(1ll*p*lamxl%mod+1ll*(mod+1-p)*lamxr%mod)%mod);return y;}
if(!y){MUL(x,(1ll*p*lamyl%mod+1ll*(mod+1-p)*lamyr%mod)%mod);return x;}
int z=++cnt;seg[z].tag=1;
int XL=seg[seg[x].lson].sum,XR=seg[seg[x].rson].sum,YL=seg[seg[y].lson].sum,YR=seg[seg[y].rson].sum;
seg[z].lson=merge(seg[x].lson,seg[y].lson,lamxl,(lamxr+XR)%mod,lamyl,(lamyr+YR)%mod,p);
seg[z].rson=merge(seg[x].rson,seg[y].rson,(lamxl+XL)%mod,lamxr,(lamyl+YL)%mod,lamyr,p);
seg[z].sum=(seg[seg[z].lson].sum+seg[seg[z].rson].sum)%mod;
return z;
}
void dfs(int x){
if(v[x].empty())modify(rt[x],1,m,p[x]);
else if(v[x].size()==1)dfs(v[x][0]),rt[x]=rt[v[x][0]];
else dfs(v[x][0]),dfs(v[x][1]),rt[x]=merge(rt[v[x][0]],rt[v[x][1]],0,0,0,0,p[x]);
}
void iterate(int x,int l,int r){
if(l==r)(res+=1ll*l*u[l-1]%mod*seg[x].sum%mod*seg[x].sum%mod)%=mod;
else pushdown(x),iterate(seg[x].lson,l,mid),iterate(seg[x].rson,mid+1,r);
}
int main(){
scanf("%d",&n);
for(int i=1,x;i<=n;i++)scanf("%d",&x),v[x].push_back(i);
for(int x=1;x<=n;x++){
scanf("%d",&p[x]);
if(v[x].empty())u.push_back(p[x]);
else p[x]=1ll*p[x]*inv10k%mod;
}
sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin());
for(int x=1;x<=n;x++)if(v[x].empty())p[x]=lower_bound(u.begin(),u.end(),p[x])-u.begin()+1;
dfs(1),iterate(rt[1],1,m);
printf("%d\n",res);
return 0;
}
```
## I.IV.[[NOI2020]命运](https://www.luogu.com.cn/problem/P6773)
半年前水了份 $n^2$ 暴力，没想到过了出题人用脚造的数据。这里是正解。
考虑DP。因为若两条路径呈包含关系，则更长的那条显然没用，于是设 $f_{i,j}$ 表示所有下端在 $i$ 子树内且未被满足的路径中，上端最深的那条的深度。明显，要且仅要满足这条路径的限制，子树中所有现行的路径都可以被满足。
考虑转移。假设我们现在想要合并某父亲 $x$ 与儿子 $y$。
1. 边 $(x,y)$ 选择。
则所有 $x$ 中满足 $i\leq dep_x$ 的 $f_{x,i}$，都可以从 $y$ 中所有满足 $j\leq dep_y$ 的 $f_{y,j}$ 转移而来。
于是有 $f_{x,i}\leftarrow f_{x,i}\times\sum\limits_{j=0}^{dep_y}f_{y,j}$。
2. 边 $(x,y)$ 不选。
则最深的那条可以来自于 $x$，亦可来自于 $y$。
于是有 $f_{x,\max\{i,j\}}\leftarrow f_{x,i}\times f_{y,j}$。
变换形式，得到
$f_{x,i}\leftarrow\Big(f_{x,i}\sum\limits_{j=0}^{i-1}f_{y,j}\Big)+\Big(f_{y,i}\sum\limits_{j=0}^{i-1}f_{x,j}\Big)+f_{x,i}f_{y,i}$
最后，两坨东西怼一块，得到最终转移式
$f_{x,i}\leftarrow f_{x,i}\Big(\sum\limits_{j=0}^{i-1}f_{y,j}+\sum\limits_{j=0}^{dep_y}f_{y,j}\Big)+\Big(f_{y,i}\sum\limits_{j=0}^{i-1}f_{x,j}\Big)+f_{x,i}f_{y,i}$
考虑用线段树合并维护。那三大坨前缀和，上界是 $dep_y$ 的那坨对于不同的 $i$ 是相同的，可以直接在 $y$ 的线段树内维护；剩下的两坨，在合并的时候顺便维护一下即可。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,dep[500100],DP,cnt,rt[500100];
vector<int>v[500100],u[500100];
void dfs1(int x,int fa){
dep[x]=dep[fa]+1,DP=max(DP,dep[x]);
for(auto y:v[x])if(y!=fa)dfs1(y,x);
}
#define mid ((l+r)>>1)
struct SegTree{
int lson,rson,sum,tag;
}seg[20010000];
void MUL(int x,int y){seg[x].sum=1ll*seg[x].sum*y%mod,seg[x].tag=1ll*seg[x].tag*y%mod;}
void pushdown(int x){MUL(seg[x].lson,seg[x].tag),MUL(seg[x].rson,seg[x].tag),seg[x].tag=1;}
void pushup(int x){seg[x].sum=(seg[seg[x].lson].sum+seg[seg[x].rson].sum)%mod;}
void setbound(int &x,int l,int r,int P,int sum){
if(l>P)return;
if(r<P){x=0;return;}
if(!x)x=++cnt,seg[x].tag=1;
if(l==r){(seg[x].sum+=sum)%=mod;return;}
pushdown(x),setbound(seg[x].rson,mid+1,r,P,(sum+seg[seg[x].lson].sum)%mod),setbound(seg[x].lson,l,mid,P,sum),pushup(x);
}
void setempty(int &x,int l,int r){
if(!x)x=++cnt,seg[x].tag=1;seg[x].sum++;
if(l!=r)setempty(seg[x].lson,l,mid);
}
int query(int x,int l,int r,int P){
if(l>P||!x)return 0;
if(r<=P)return seg[x].sum;
pushdown(x);return (query(seg[x].lson,l,mid,P)+query(seg[x].rson,mid+1,r,P))%mod;
}
void merge(int &x,int y,int l,int r,int sumx,int sumy){
if(!x){MUL(y,sumx),x=y;return;}
if(!y){MUL(x,sumy);return;}
if(l==r){seg[x].sum=(1ll*seg[x].sum*sumy%mod+1ll*seg[y].sum*sumx%mod+1ll*seg[x].sum*seg[y].sum%mod)%mod;return;}
pushdown(x),pushdown(y);
merge(seg[x].rson,seg[y].rson,mid+1,r,(sumx+seg[seg[x].lson].sum)%mod,(sumy+seg[seg[y].lson].sum)%mod);
merge(seg[x].lson,seg[y].lson,l,mid,sumx,sumy);
pushup(x);
}
void iterate(int x,int l,int r){
if(!x)return;
printf("%d:[%d,%d]:%d\n",x,l,r,seg[x].sum);
iterate(seg[x].lson,l,mid),iterate(seg[x].rson,mid+1,r);
}
void dfs2(int x,int fa){
setempty(rt[x],0,DP);
for(auto y:v[x])if(y!=fa)dfs2(y,x),merge(rt[x],rt[y],0,DP,0,query(rt[y],0,DP,dep[x]));
for(auto i:u[x])setbound(rt[x],0,DP,i,0);
// printf("%d:\n",x);
// iterate(rt[x],0,DP);
}
int main(){
scanf("%d",&n);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs1(1,0);
scanf("%d",&m);
for(int i=1,x,y;i<=m;i++)scanf("%d%d",&x,&y),u[y].push_back(dep[x]);
dfs2(1,0);
printf("%d\n",query(rt[1],0,DP,0));
return 0;
}
```
## I.V.[[FJOI2018]领导集团问题](https://www.luogu.com.cn/problem/P4577)
这题的难点主要是在状态的设计上。
首先，一个naive的想法是设 $f_i$ 表示节点 $i$ 子树中，强制节点 $i$ 选择的最优答案，然后使用线段树合并转移。
但是这样在合并不同子树时会出大问题。于是我们不得不更换状态。
于是我们设 $f_{i,j}$ 表示 $i$ 子树中只选择不小于 $j$ 的点的最优答案。
则显然，$i$ 不选时的 $f$ 可以直接通过所有儿子的 $f$ 求和得到。
而 $i$ 选择的时候，就是 $f_{i,a_i}$ 增加 $1$。
于是我们的操作目前便是两种：线段树合并，以及单点加一。
但是，我们发现，在单点加一后，按照DP数组的意义，所有 $j<a_i$ 的 $f_{i,j}$ 都要与 $f_{i,a_i}$ 取 $\max$。
于是我们操作一共三种：线段树合并区间和，单点加，区间取 $\max$。
但是线段树合并要适配区间操作就会很麻烦。有没有更好的方法？
我们发现，$f_i$ 数组是不增的。故我们差分后，区间取 $\max$ 操作就变成了一头一尾的单点修改。
尾部的单点修改位置很明确，就是 $a_i$；但是头部的单点修改，就需要在线段树上二分出第一个 $>f_{i,a_i}$ 的位置，然后再修改。
我们总结一下，需要支持：线段树合并，单点修改，树上二分，后缀求和。是常规操作，不说了。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[200100],m,cnt,f[200100],rt[200100];
vector<int>v[200100],u;
#define mid ((l+r)>>1)
struct node{int lson,rson,sum;}seg[6401000];
void pushup(int x){seg[x].sum=seg[seg[x].lson].sum+seg[seg[x].rson].sum;}
void modify(int &x,int l,int r,int P,int val){
if(l>P||r<P)return;if(!x)x=++cnt;
if(l==r){seg[x].sum=val;return;}
modify(seg[x].lson,l,mid,P,val),modify(seg[x].rson,mid+1,r,P,val),pushup(x);
}
void merge(int &x,int y,int l,int r){
if(!x){x=y;return;}if(!y)return;
seg[x].sum+=seg[y].sum;
if(l!=r)merge(seg[x].lson,seg[y].lson,l,mid),merge(seg[x].rson,seg[y].rson,mid+1,r);
}
int query(int x,int l,int r,int P){
if(r<P)return 0;
if(l>=P)return seg[x].sum;
return query(seg[x].lson,l,mid,P)+query(seg[x].rson,mid+1,r,P);
}
int pos(int x,int l,int r,int k){
if(l==r)return l;
if(k>=seg[seg[x].rson].sum)return pos(seg[x].lson,l,mid,k-seg[seg[x].rson].sum);
else return pos(seg[x].rson,mid+1,r,k);
}
void erase(int &x,int l,int r,int L,int R){
if(l>R||r<L)return;
if(L<=l&&r<=R){x=0;return;}
erase(seg[x].lson,l,mid,L,R),erase(seg[x].rson,mid+1,r,L,R),pushup(x);
}
void iterate(int x,int l,int r){
if(!x)return;
printf("%d:[%d,%d]:%d\n",x,l,r,seg[x].sum);
if(l!=r)iterate(seg[x].lson,l,mid),iterate(seg[x].rson,mid+1,r);
}
void dfs(int x){
for(auto y:v[x])dfs(y),merge(rt[x],rt[y],1,m);
f[x]=query(rt[x],1,m,a[x])+1;
if(seg[rt[x]].sum>f[x]){
int L=pos(rt[x],1,m,f[x]);
int vl=query(rt[x],1,m,L),vr=query(rt[x],1,m,a[x]+1);
modify(rt[x],1,m,L,vl-f[x]),erase(rt[x],1,m,L+1,a[x]-1),modify(rt[x],1,m,a[x],f[x]-vr);
}else{
int vr=query(rt[x],1,m,a[x]+1);
erase(rt[x],1,m,1,a[x]-1),modify(rt[x],1,m,a[x],f[x]-vr);
}
// printf("%d:%d\n",x,f[x]),iterate(rt[x],1,m);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),u.push_back(a[i]);
sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin());
for(int i=2,x;i<=n;i++)scanf("%d",&x),v[x].push_back(i);
for(int i=1;i<=n;i++)a[i]=lower_bound(u.begin(),u.end(),a[i])-u.begin()+1;
dfs(1),printf("%d\n",seg[rt[1]].sum);
return 0;
}
```
## I.VI.[[NOI2018] 情报中心](https://www.luogu.com.cn/problem/P4775)
神题。
考虑两条路径 $(u_1,v_1),(u_2,v_2)$。
我们设一对 $(X,Y)$ 表示这两条路径的并的起讫点。
一种情形下有 $X=\text{LCA}(u_1,v_1),Y=\text{LCA}(u_2,v_2)$（这时两条路径的LCA相同），而另一种情形下则是 $X=\text{LCA}(u_1,v_1),Y=\text{LCA}(u_1,v_2)$（这时两条路径的LCA不同）。
但是我们发现它们的路径并的权值总是可以用 $\dfrac{\text{DIS}(u_1,v_1)+\text{DIS}(u_2,v_2)+\text{DIS}(u_1,u_2)+\text{DIS}(v_1,v_2)}{2}$ 来表示，无论哪种情况。
于是我们设 $\text{cost}(u,v)=\text{DIS}(u,v)-2w$。这样，选择路径 $(u_1,v_1),(u_2,v_2)$ 时的代价便可以简单用 $\dfrac{\text{cost}(u_1,v_1)+\text{cost}(u_2,v_2)+\text{DIS}(u_1,u_2)+\text{DIS}(v_1,v_2)}{2}$ 表示。于是两种情况的代价便被统一了。
现在不妨令 $X$ 的深度不小于 $Y$。则 $u_1,u_2$ 必在 $X$ 的两个不同子树中，而 $v_1,v_2$ 必定在 $X$ 的子树外。
于是我们考虑遍历整棵树，在每个节点 $X$ 处统计这样的两条路径的答案。
考虑 $\text{DIS}(u_1,u_2)$，此时便可以被拆作 $\text{dep}_{u_1}+\text{dep}_{u_2}-2\text{dep}_X$ 来简单计算。
我们将 $\text{dep}_{u_1}+\text{cost}(u_1,v_1)$ 记录在 $v_1$ 处，起名叫 $\text{val}_{v_1}$。同理将 $\text{dep}_{u_2}+\text{cost}(u_2,v_2)$ 记作 $\text{val}_{v_2}$ 记录在 $v_2$ 处。这样，贡献便是 $\dfrac{\text{val}_{v_1}+\text{val}_{v_2}+\text{DIS}(v_1,v_2)}{2}$。
这时，假如我们把 $\text{val}_v$ 看作是从 $v$ 点新建出来的一条长度为 $\text{val}_v$ 的边的话，则上述式子就等价于两点间距离。
然后明显对于 $X$ 的每棵儿子的子树，所有合法的 $v$ 都来自于一个集合。于是我们就要支持合并集合，求出集合中两点距离 $\max$。
这是经典模型了，结论是并集的直径端点来自于直径端点的并集。
虽然这个结论在边权为负的情形下不成立，但是原树中的边都非负，而新建的两条边边权虽可能为负，但是显然每条路径中都会出现且仅出现两次这种边，那么就预先加上一个 $\infty$ 就能同边权非负一样处理了。
但是我们还需要保证 $X$ 要比 $Y$ 小。画出图来的话就会发现在路径的LCA处从集合中删去路径端点即可。
而正是因为要支持从集合中删除元素，我们才不得不使用线段树合并而不是直接记录一对数表示集合的直径。
时间复杂度 $O(n\log n)$。
虽然这样，但是非常卡常，需要尽可能压榨常数。
但是好像不管怎样#6总会莫名其妙挂。
一开始以为是常卡得不够优美，所以绞尽脑汁卡，卡不过。
然后数据花了几分钟下下来一测，挂了。
手动排查发现是爆栈。在本地开栈后测了好几次都不到8s。
虽然想着OJ应该不会在这方面出纰漏，但是还是觉得实在没啥可优化的了，于是便写了非递归式dfs。
事实证明这个东西的特点有两个：1.非常糟糕。2.没啥用。
最后我实在受不了了，C++17,Ofast,LOJ，走起。
7981ms，过了。
6号点的数据是链，个人觉得是线段树合并写丑了。
觉得洛谷是不指望能过了……
更何况除了6号点8s+，其它点最大的一个都才6s不到。
不知道自己是哪里去世了。
------
在写完上面的丧气话后1min，我看到洛谷评论区中有老哥跟我一样挂了。
那位老哥说是又交了一发然后因为评测姬波动卡过去了。
然后我就随便又交了一发。不过以前开的是C++17,O2，这回就直接用的是无优化的C++11。
然后过了。
???
那位苦心孤诣去优化有什么意思？
垃圾数据，散了散了。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll fni=0xc0c0c0c0c0c0c0c0;
int T,n,m,head[50100],cnt;
struct node{int to,next,val;}edge[100100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
int st[100100][17],LG[100100],tot,dep[50100],fir[50100],rif[50100];
ll dis[50100];
int stk[50100],I[50100],STK;
void dfs1(){
stk[STK=1]=1,I[STK]=head[1],st[++tot][0]=1,fir[1]=tot;
while(true){
while(I[STK]==-1){
rif[stk[STK]]=tot;
if(!--STK)break;
st[++tot][0]=stk[STK];
}
if(!STK)break;
if(edge[I[STK]].to==stk[STK-1]){I[STK]=edge[I[STK]].next;continue;}
stk[STK+1]=edge[I[STK]].to;
dis[stk[STK+1]]=dis[stk[STK]]+edge[I[STK]].val;
dep[stk[STK+1]]=dep[stk[STK]]+1;
I[STK]=edge[I[STK]].next;
STK++,I[STK]=head[stk[STK]];
st[++tot][0]=stk[STK],fir[stk[STK]]=tot;
}
}
int MIN(int x,int y){return dep[x]<dep[y]?x:y;}
int LCA(int x,int y){
x=fir[x],y=fir[y];
if(x>y)swap(x,y);
int k=LG[y-x+1];
return MIN(st[x][k],st[y-(1<<k)+1][k]);
}
ll DIS(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
int P[200100];
ll V[200100],res;
template<typename T>void chmx(T&x,T y){if(x<y)x=y;}
struct Dia{
int x,y;
ll val;
Dia(){x=y=0,val=fni;}
Dia(int X){x=X,y=0,val=fni;}
Dia(int X,int Y){
x=X,y=Y;
if(!y)val=fni;
else if(!x)swap(x,y),val=fni;
else val=DIS(P[x],P[y])+V[x]+V[y];
}
friend bool operator<(const Dia u,const Dia v){return u.val<v.val;}
friend Dia operator+(const Dia&u,const Dia&v){
if(!u.x)return v;
if(!v.x)return u;
Dia w=max(u,v);
chmx(w,Dia(u.x,v.x));
chmx(w,Dia(u.x,v.y));
chmx(w,Dia(u.y,v.x));
chmx(w,Dia(u.y,v.y));
return w;
}
friend ll operator*(const Dia&u,const Dia&v){
if(!u.x||!v.x)return fni;
ll d=fni;
chmx(d,Dia(u.x,v.x).val);
chmx(d,Dia(u.x,v.y).val);
chmx(d,Dia(u.y,v.x).val);
chmx(d,Dia(u.y,v.y).val);
return d;
}
};
vector<int>v[50100];
vector<pair<int,int> >u[50100];
int num,rt[50100],bin[4000100],tp;
int Newnode(){return tp?bin[tp--]:++num;}
#define mid ((l+r)>>1)
struct SegTree{int lson,rson;Dia val;}seg[4000100];
void turnon(int&x,int l,int r,int P){
if(!x)x=Newnode();
if(l==r)return void(seg[x].val=Dia(P));
if(P<=mid)turnon(seg[x].lson,l,mid,P);else turnon(seg[x].rson,mid+1,r,P);
seg[x].val=seg[seg[x].lson].val+seg[seg[x].rson].val;
}
void turnoff(int&x,int l,int r,int P){
if(l==r)return seg[x].val=Dia(),bin[++tp]=x,x=0,void();
if(P<=mid)turnoff(seg[x].lson,l,mid,P);else turnoff(seg[x].rson,mid+1,r,P);
if(!seg[x].lson&&!seg[x].rson)bin[++tp]=x,x=0;else seg[x].val=seg[seg[x].lson].val+seg[seg[x].rson].val;
}
void merge(int&x,int&y){
if(!y)return;
if(!x)return void(swap(x,y));
merge(seg[x].lson,seg[y].lson),merge(seg[x].rson,seg[y].rson);
seg[x].val=seg[x].val+seg[y].val,bin[++tp]=y,y=0;
}
void clear(int&x,int l,int r){if(l!=r)clear(seg[x].lson,l,mid),clear(seg[x].rson,mid+1,r);x=0;}
int J[50100];
void func(int x){
stk[++STK]=x,I[STK]=head[x],J[STK]=0;
sort(u[x].begin(),u[x].end());
for(auto i:v[x])turnon(rt[x],1,2*m,i);
while(J[STK]<u[x].size()&&u[x][J[STK]].first==fir[x])turnoff(rt[x],1,2*m,u[x][J[STK]++].second);
res=max(res,seg[rt[x]].val.val-2*dis[x]);
}
void dfs(){
STK=0,func(1);
while(true){
while(I[STK]==-1){
v[stk[STK]].clear(),u[stk[STK]].clear();
if(!--STK)break;
int x=stk[STK],y=stk[STK+1];
while(J[STK]<u[x].size()&&u[x][J[STK]].first<=rif[y])turnoff(rt[y],1,2*m,u[x][J[STK]++].second);
res=max(res,seg[rt[x]].val*seg[rt[y]].val-2*dis[x]);
merge(rt[x],rt[y]);
}
if(!STK)break;
if(edge[I[STK]].to==stk[STK-1]){I[STK]=edge[I[STK]].next;continue;}
int y=edge[I[STK]].to;
I[STK]=edge[I[STK]].next,func(y);
}
}
template<typename T>void read(T&x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
template<typename T>void print(T x){
if(x<0)putchar('-'),print(-x);
else if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
// freopen("center.in","r",stdin);
// freopen("center.out","w",stdout);
read(T);
while(T--){
read(n),res=fni;
for(int i=1;i<=n;i++)head[i]=-1;cnt=0;
for(int i=1,x,y,z;i<n;i++)read(x),read(y),read(z),ae(x,y,z);
tot=0;
dfs1();
for(int i=2;i<=tot;i++)LG[i]=LG[i>>1]+1;
// printf("%d,%d\n",tot,LG[tot]);
for(int j=1;j<=LG[tot];j++)for(int i=1;i+(1<<j)-1<=tot;i++)st[i][j]=MIN(st[i][j-1],st[i+(1<<(j-1))][j-1]);
read(m);
for(int i=1;i<=m;i++){
ll cost;
read(P[2*i-1]),read(P[2*i]),read(cost);
cost=DIS(P[2*i-1],P[2*i])-2*cost;
V[2*i-1]=dis[P[2*i]]+cost;
V[2*i]=dis[P[2*i-1]]+cost;
// printf("(%d,%d)\n",V[2*i-1],V[2*i]);
v[P[2*i-1]].push_back(2*i);
v[P[2*i]].push_back(2*i-1);
// printf("%d\n",LCA(P[2*i-1],P[2*i]));
u[LCA(P[2*i-1],P[2*i])].emplace_back(fir[P[2*i-1]],2*i);
u[LCA(P[2*i-1],P[2*i])].emplace_back(fir[P[2*i]],2*i-1);
}
tp=num=0,dfs(),clear(rt[1],1,2*m);
if(res==fni)putchar('F');else print(res/2);putchar('\n');
}
return 0;
}
```
# II.区间取最值数据结构
区间取最值数据结构是一类支持区间所有数对某个数取 $\min/\max$，以及其它常规区间操作的数据结构。
最常见的区间最值数据结构是**吉司机线段树**，又名 `Segment Tree Beats!`，~~吊打线段树~~？
以下用 `SegBeats` 来简称这种数据结构。
我们以区间取 $\min$、区间求和为例。
其具体实现是，在线段树的每个节点上存储区间最大值、区间次大值、区间最大值出现次数、区间和。显然，所有东西都可以简单维护。
然后，考虑区间取 $\min$。在线段树上，大区间被拆成了许多小区间。考虑其中某一个小区间。
假设现在是区间关于某个值 $x$ 取 $\min$。则，若区间最大值不大于 $x$，显然可以直接 `return` 了；
若 $x$ 比次大值大、比最大值小，则其只会作用于最大值一个值，因此可以直接打 `tag`，只修改最小值；
若 $x$ 小于等于次大值，则修改不很简单，我们继续递归入子区间修改。
可以被证明，若不存在区间修改，复杂度是 $O(n\log n)$ 的；否则，复杂度 $O(n\log^2n)$。
~~证明？直接用就行了~~
推荐在阅读完II后紧接IX.历史最值数据结构使用。
## II.I.[CF1290E Cartesian Tree](https://www.luogu.com.cn/problem/CF1290E)
并非一道很板的题，但是是可以被想出的。
考虑把笛卡尔树求出其中序遍历，则每个节点的子树是上面一段区间 $[l_i,r_i]$。
考虑往中序遍历序列中某个位置 $p$ **之后**插入一个数 $k$。显然，依照定义，这个数必定大于原序列中所有数。考虑插入后每个 $[l_i,r_i]$ 的变化。
我们发现，对于 $p$ 及 $p$ 左侧的所有位置 $i$，其 $l_i$ 不变，$r_i$ 与 $p$ 取 $\min$；对于新插入的这个数本身，其 $l=1$，$r=k$；对于 $p$ 右侧所有 $i$，因为多插入了一个数，所以所有 $l,r$ 先增加 $1$，然后 $l$ 与 $p+2$ 取 $\max$。
我们发现，因为我们要求的是 $\sum\limits_{i=1}^kr_i-l_i+1$，故其可以被拆成 $(\sum r)-(\sum l)+k$。$\sum r$ 可简单维护，而 $-\sum l$ 在整个**序列翻转**后，便可以同 $\sum r$ 一样求出，两者求和后只需在最后减去一个 $k^2$ 就行了。
于是我们只需处理对于 $r$ 的操作就行了。
我们发现，要执行的是前缀取 $\min$，单点赋值，后缀 $+1$。则直接使用 `SegBeats` 就搞定了。
需要注意的是，没有被赋值过的位置要被忽略，就像动态开点线段树里面的空子树一样处理。
因为这里有后缀加，所以复杂度有 $n\log^2n$ 的上界。然而根本跑不满，所以 `SegBeats` 大可以在 $5\times10^5$ 这种数据范围下随便用，特别是在本题还是 $1.5\times10^5$，`5s` 的。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[150100],p[150100];
ll res[150100];
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegBeat{
int mx,mmx,mxc,tag,gat,sz;ll sum;
SegBeat(){sum=tag=-1,sz=gat=0;}
}seg[600100];
void pushup(int x){
if(seg[lson].sum==-1&&seg[rson].sum==-1){seg[x].sum=-1;return;}
if(seg[lson].sum==-1){seg[x]=seg[rson],seg[x].gat=0,seg[x].tag=-1;return;}
if(seg[rson].sum==-1){seg[x]=seg[lson],seg[x].gat=0,seg[x].tag=-1;return;}
seg[x].mx=max(seg[lson].mx,seg[rson].mx),seg[x].mmx=-1,seg[x].mxc=0,seg[x].sum=seg[lson].sum+seg[rson].sum,seg[x].sz=seg[lson].sz+seg[rson].sz;
if(seg[x].mx!=seg[lson].mx)seg[x].mmx=max(seg[x].mmx,seg[lson].mx);else seg[x].mxc+=seg[lson].mxc,seg[x].mmx=max(seg[x].mmx,seg[lson].mmx);
if(seg[x].mx!=seg[rson].mx)seg[x].mmx=max(seg[x].mmx,seg[rson].mx);else seg[x].mxc+=seg[rson].mxc,seg[x].mmx=max(seg[x].mmx,seg[rson].mmx);
}
void MOD(int x,int y){seg[x].sum-=1ll*(seg[x].mx-y)*seg[x].mxc,seg[x].mx=seg[x].tag=y;}
void ADD(int x,int y){seg[x].mx+=y,seg[x].gat+=y,seg[x].mmx+=y,seg[x].sum+=1ll*seg[x].sz*y;if(seg[x].tag!=-1)seg[x].tag+=y;}
void pushdown(int x){
if(seg[lson].sum!=-1)ADD(lson,seg[x].gat);
if(seg[rson].sum!=-1)ADD(rson,seg[x].gat);
seg[x].gat=0;
if(seg[x].tag==-1)return;
if(seg[lson].sum!=-1&&seg[lson].mx>seg[x].tag)MOD(lson,seg[x].tag);
if(seg[rson].sum!=-1&&seg[rson].mx>seg[x].tag)MOD(rson,seg[x].tag);
seg[x].tag=-1;
}
void modifypos(int x,int l,int r,int P,int val){
if(l>P||r<P)return;
if(l==r){seg[x].mx=val,seg[x].mmx=-1,seg[x].sum=val,seg[x].mxc=1,seg[x].sz=1;return;}
pushdown(x),modifypos(lson,l,mid,P,val),modifypos(rson,mid+1,r,P,val),pushup(x);
}
void modifymn(int x,int l,int r,int L,int R,int val){
if(seg[x].mx<=val||seg[x].sum==-1||l>R||r<L)return;
if(L<=l&&r<=R&&seg[x].mmx<val){MOD(x,val);return;}
pushdown(x),modifymn(lson,l,mid,L,R,val),modifymn(rson,mid+1,r,L,R,val),pushup(x);
}
void modifyshift(int x,int l,int r,int L,int R){
if(l>R||r<L||seg[x].sum==-1)return;
if(L<=l&&r<=R){ADD(x,1);return;}
pushdown(x),modifyshift(lson,l,mid,L,R),modifyshift(rson,mid+1,r,L,R),pushup(x);
}
void clear(int x,int l,int r){
seg[x]=SegBeat();
if(l!=r)clear(lson,l,mid),clear(rson,mid+1,r);
}
/*void iterate(int x,int l,int r){
if(seg[x].sum==-1)return;
printf("[%d,%d]:MX:%d CM:%d MM:%d SM:%d SZ:%d GT:%d TG:%d\n",l,r,seg[x].mx,seg[x].mxc,seg[x].mmx,seg[x].sum,seg[x].sz,seg[x].gat,seg[x].tag);
if(l!=r)iterate(lson,l,mid),iterate(rson,mid+1,r);
}
void etareti(int x,int l,int r){
if(seg[x].sum==-1)return;
if(l!=r)pushdown(x),etareti(lson,l,mid),etareti(rson,mid+1,r),pushup(x);
else printf("(%d:%d)",l,seg[x].mx);
}*/
int t[200100];
void BITADD(int x){while(x<=n)t[x]++,x+=x&-x;}
int BITSUM(int x){int ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
void func(){
clear(1,1,n),memset(t,0,sizeof(t));
for(int i=1;i<=n;i++){
int Rmax=BITSUM(p[i]);
modifymn(1,1,n,1,p[i]-1,Rmax);
modifypos(1,1,n,p[i],i);
modifyshift(1,1,n,p[i]+1,n);
// printf("%d\n",seg[1].sum);
res[i]+=seg[1].sum;
BITADD(p[i]);
// iterate(1,1,n),puts("");
// etareti(1,1,n),puts("");
// iterate(1,1,n),puts("");
}
}
inline void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(ll x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
read(n);
for(int i=1;i<=n;i++)read(a[i]),p[a[i]]=i;
func();
reverse(a+1,a+n+1);for(int i=1;i<=n;i++)p[a[i]]=i;
func();
for(int i=1;i<=n;i++)print(res[i]-1ll*i*i),putchar('\n');
return 0;
}
```
## II.II.[BZOJ#4695. 最假女选手](https://darkbzoj.tk/problem/4695)
实际上是 `SegBeats` 的模板。
~~经过压行后甚至比上一题还要短是怎么回事啊喂~~
~~甚至能够1A~~
~~53行极短代码，你值得拥有~~
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int a[500100],n,m;
struct SegTree{int mx,smx,mn,smn,cmx,cmn,tagsm;ll sum;}seg[2001000];
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
#define X x,l,r
#define LSON lson,l,mid
#define RSON rson,mid+1,r
void ADD(int x,int l,int r,int y){seg[x].mx+=y,seg[x].mn+=y;if(seg[x].smx!=-inf)seg[x].smx+=y;if(seg[x].smn!=inf)seg[x].smn+=y;seg[x].sum+=1ll*(r-l+1)*y,seg[x].tagsm+=y;}
void MX(int x,int y){if(seg[x].mn==seg[x].mx)seg[x].mn=y;if(seg[x].smn==seg[x].mx)seg[x].smn=y;seg[x].sum+=1ll*seg[x].cmx*(y-seg[x].mx),seg[x].mx=y;}
void MN(int x,int y){if(seg[x].mx==seg[x].mn)seg[x].mx=y;if(seg[x].smx==seg[x].mn)seg[x].smx=y;seg[x].sum-=1ll*seg[x].cmn*(seg[x].mn-y),seg[x].mn=y;}
void pushdown(int x,int l,int r){
ADD(LSON,seg[x].tagsm),ADD(RSON,seg[x].tagsm),seg[x].tagsm=0;
if(seg[lson].mx>seg[x].mx)MX(lson,seg[x].mx);if(seg[rson].mx>seg[x].mx)MX(rson,seg[x].mx);
if(seg[lson].mn<seg[x].mn)MN(lson,seg[x].mn);if(seg[rson].mn<seg[x].mn)MN(rson,seg[x].mn);
}
void pushup(int x){
seg[x].sum=seg[lson].sum+seg[rson].sum,seg[x].mx=max(seg[lson].mx,seg[rson].mx),seg[x].mn=min(seg[lson].mn,seg[rson].mn),seg[x].cmx=seg[x].cmn=0;
if(seg[lson].mx==seg[x].mx)seg[x].cmx+=seg[lson].cmx;if(seg[rson].mx==seg[x].mx)seg[x].cmx+=seg[rson].cmx;
if(seg[lson].mn==seg[x].mn)seg[x].cmn+=seg[lson].cmn;if(seg[rson].mn==seg[x].mn)seg[x].cmn+=seg[rson].cmn;
seg[x].smx=max(seg[x].mx==seg[lson].mx?seg[lson].smx:seg[lson].mx,seg[x].mx==seg[rson].mx?seg[rson].smx:seg[rson].mx);
seg[x].smn=min(seg[x].mn==seg[lson].mn?seg[lson].smn:seg[lson].mn,seg[x].mn==seg[rson].mn?seg[rson].smn:seg[rson].mn);
}
void build(int x,int l,int r){if(l==r){seg[x].sum=seg[x].mx=seg[x].mn=a[l],seg[x].smx=-inf,seg[x].smn=inf,seg[x].cmx=seg[x].cmn=1;return;}build(LSON),build(RSON),pushup(x);}
void modifyadd(int x,int l,int r,int L,int R,int val){if(l>R||r<L)return;if(L<=l&&r<=R){ADD(X,val);return;}pushdown(X),modifyadd(LSON,L,R,val),modifyadd(RSON,L,R,val),pushup(x);}
void checkmax(int x,int l,int r,int L,int R,int val){
if(l>R||r<L||seg[x].mn>=val)return;if(L<=l&&r<=R&&seg[x].smn>val){MN(x,val);return;}
pushdown(X),checkmax(LSON,L,R,val),checkmax(RSON,L,R,val),pushup(x);
}
void checkmin(int x,int l,int r,int L,int R,int val){
if(l>R||r<L||seg[x].mx<=val)return;if(L<=l&&r<=R&&seg[x].smx<val){MX(x,val);return;}
pushdown(X),checkmin(LSON,L,R,val),checkmin(RSON,L,R,val),pushup(x);
}
ll asksum(int x,int l,int r,int L,int R){if(l>R||r<L)return 0;if(L<=l&&r<=R)return seg[x].sum;pushdown(X);return asksum(LSON,L,R)+asksum(RSON,L,R);}
int askmx(int x,int l,int r,int L,int R){if(l>R||r<L)return -inf;if(L<=l&&r<=R)return seg[x].mx;pushdown(X);return max(askmx(LSON,L,R),askmx(RSON,L,R));}
int askmn(int x,int l,int r,int L,int R){if(l>R||r<L)return inf;if(L<=l&&r<=R)return seg[x].mn;pushdown(X);return min(askmn(LSON,L,R),askmn(RSON,L,R));}
int main(){
scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&a[i]);build(1,1,n);
scanf("%d",&m);for(int i=1,tp,l,r,x;i<=m;i++){
scanf("%d%d%d",&tp,&l,&r);
if(tp==1)scanf("%d",&x),modifyadd(1,1,n,l,r,x);
if(tp==2)scanf("%d",&x),checkmax(1,1,n,l,r,x);
if(tp==3)scanf("%d",&x),checkmin(1,1,n,l,r,x);
if(tp==4)printf("%lld\n",asksum(1,1,n,l,r));
if(tp==5)printf("%d\n",askmx(1,1,n,l,r));
if(tp==6)printf("%d\n",askmn(1,1,n,l,r));
}
return 0;
}
```
## II.III.[[UOJ#515]【UR #19】前进四](uoj.ac/problem/515)
一个线段树，然后 `pushup` 时 $\log n$ 递归的 $n\log^2n$ 做法应该是显然的。但是 $10^6$ 明显不可能过。
注意到题目没有强制在线。于是考虑离线。
离线就要换成时间顺序以外的另一种顺序。容易想到倒序遍历数组。
于是我们便倒序遍历数组，同时维护一个关于时间的数据结构，每个位上储存当前时刻的后缀 $\min$ 及不同后缀 $\min$ 数。这样询问的时候就直接调出询问的时刻的结果即可。
下面考虑此数据结构要支持什么。明显是区间取 $\min$ 及历史 $\min$ 数量。前者是常规 `SegBeats` 操作，后者可以在前者基础上简单统计得到。
因为仅有取 $\min$ 操作，复杂度为 $n\log n$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,Q,res[1001000];
vector<int>q[1001000];
vector<pair<int,int> >p[1001000];
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{
int mx,semx,tagtim;
SegTree(){mx=0x3f3f3f3f,semx=tagtim=0;}
}seg[4001000];
void pushup(int x){
seg[x].mx=max(seg[lson].mx,seg[rson].mx);
seg[x].semx=max(seg[x].mx!=seg[lson].mx?seg[lson].mx:seg[lson].semx,seg[x].mx!=seg[rson].mx?seg[rson].mx:seg[rson].semx);
}
void CHMN(int x,int val,int tim){if(seg[x].mx>val)seg[x].mx=val,seg[x].tagtim+=tim;}
void pushdown(int x){
if(!seg[x].tagtim)return;
CHMN(lson,seg[x].mx,seg[x].tagtim),CHMN(rson,seg[x].mx,seg[x].tagtim),seg[x].tagtim=0;
}
void modifymin(int x,int l,int r,int L,int R,int val){
if(l>R||r<L||val>=seg[x].mx)return;
if(L<=l&&r<=R&&seg[x].semx<val)CHMN(x,val,1);
else pushdown(x),modifymin(lson,l,mid,L,R,val),modifymin(rson,mid+1,r,L,R,val),pushup(x);
// printf("%d[%d,%d]:%d,%d,%d\n",x,l,r,seg[x].mx,seg[x].semx,seg[x].mxp);
}
int query(int x,int l,int r,int P){
if(l==r)return seg[x].tagtim;
pushdown(x);
return P<=mid?query(lson,l,mid,P):query(rson,mid+1,r,P);
}
void build(int x,int l,int r){
if(l!=r)build(lson,l,mid),build(rson,mid+1,r),pushup(x);
}
inline void read(int &x){
x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
inline void print(int x){
if(x<=9)putchar('0'+x);
else print(x/10),putchar('0'+x%10);
}
int main(){
read(n),read(m);
for(int i=1,x;i<=n;i++)read(x),p[i].emplace_back(1,x);
for(int i=1,x,y,z;i<=m;i++){
read(x),read(y);
if(x==1)read(z),p[y].emplace_back(Q+1,z);
else q[y].push_back(++Q);
}
for(int i=n;i;i--){
// printf("%d:\n",i);
for(int j=0;j<p[i].size();j++)modifymin(1,1,Q,p[i][j].first,j+1==p[i].size()?Q:p[i][j+1].first-1,p[i][j].second);
for(auto j:q[i])res[j]=query(1,1,Q,j);
}
for(int i=1;i<=Q;i++)print(res[i]),putchar('\n');
return 0;
}
```
# III.李超线段树
李超线段树是一种可以维护**动态凸包**的线段树。更准确地说，其可以支持的常规操作有两种：
1. 在平面直角坐标系中插入一条线段。
2. 询问在坐标系中的一个点 $(x,+\infty)$ 向下看，能看到的点的坐标。换句话说，是一条自无穷高处引下的垂线与所有线段的交点中最高的那个点。
其具体实现如下：
我们以 $x$ 坐标为下标，建一棵线段树（可能需要离散化）。然后，在线段树的每个区间上，我们维护所有完整地包含该区间的线段中，在该区间的中点处最高的那条。具体而言，当我们插入一条线段时，首先要把它在线段树上拆作众多小区间。当递归到某个完整的区间时，考虑将其与该区间上本来记录的中点处最高线段做比较。明显，共有三种可能：
1. 新插入的线段严格不低于原本线段。此时直接替换就行。
2. 新插入的线段严格不高于原本线段。此时直接不替换就行。
3. 新插入的线段与原本线段有交。此时，先在当前区间中记录中点更高的那条，然后明显，在其一个子区间内，更高的一定是当前区间中记录的线段，可以不管；而在其另一个子区间中，更高的就不一定是它了，此时要递归入该子区间继续修改。
下面考虑分析复杂度。显然，如果插入的全部是**直线**，复杂度为 $n\log n$，因为两个子区间中最多访问其中一个；而如果我们插入的全是**线段**，因为要先拆到各个子区间上，所以复杂度就为 $n\log^2n$。
然后询问时就仿照标记永久化，直接在一路上的区间处用大区间上记录的线段更新即可。明显是 $O(n\log n)$ 的。
## III.I.[[JSOI2008]Blue Mary开公司](https://www.luogu.com.cn/problem/P4254)
是板题，甚至插入的都不是线段而是直线，就更好处理了。
真的很好写。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int lim=50000;
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
struct SegTree{double lv,rv;}seg[200100];
double calc(double lv,double rv,int l,int r,int P){return lv+(rv-lv)/(r-l)*(P-l);}
void modify(int x,int l,int r,double LV,double RV){
if(LV+RV>seg[x].lv+seg[x].rv)swap(seg[x].lv,LV),swap(seg[x].rv,RV);
if(l==r)return;
if(LV>seg[x].lv)modify(lson,l,mid,LV,calc(LV,RV,l,r,mid));
if(RV>seg[x].rv)modify(rson,mid+1,r,calc(LV,RV,l,r,mid+1),RV);
}
double query(int x,int l,int r,int P){
if(l>P||r<P)return 0;
double ret=calc(seg[x].lv,seg[x].rv,l,r,P);
if(l!=r)ret=max(ret,query(lson,l,mid,P)),ret=max(ret,query(rson,mid+1,r,P));
return ret;
}
char s[10];
int T;
int main(){
scanf("%d",&T);
for(int i=1;i<=T;i++){
scanf("%s",s);
if(s[0]=='Q'){int x;scanf("%d",&x);printf("%d\n",(int)(query(1,1,lim,x)/100));}
else{double l,r;scanf("%lf%lf",&l,&r),r=l+(lim-1)*r;modify(1,1,lim,l,r);}
}
return 0;
}
```
## III.II.[[SDOI2016]游戏](https://www.luogu.com.cn/problem/P4069)
明显，一条从 $x$ 到 $y$ 的路径可以被拆作两条从LCA下来的路径，并且路径上每个点被写上的数是关于其深度的一次函数。
于是就树剖套李超树就行了。
但是有个问题，李超树不是只支持单点询问吗，怎么这里又支持区间了呢？
我们发现，对于一条线段，其与我们询问区间可能有三种关系：相离，此时不需考虑；被完全包含于询问区间内，此时最小值一定在端点处取得，就直接用数据结构维护，插入线段时只处理两个端点，询问区间时询问所有被包含于其中的端点，无论是BIT还是常规线段树都可以轻松解决。
而剩下一种就是该线段不完全被包含于询问区间内，但依据单调性最优点一定处于端点位，所以就直接在李超树上询问端点处的最优答案即可。
复杂度 $O(n\log^3n)$。但是，李超树**常数极小**，配上树剖，仍然能搞过去。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=123456789123456789ll;
int n,m,head[100100],cnt;
struct node{int to,next,val;}edge[200100];
void ae(int u,int v,int w){
edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=w,head[v]=cnt++;
}
int fa[100100],dep[100100],son[100100],sz[100100],dfn[100100],rev[100100],top[100100],tot;
ll dis[100100];
void dfs1(int x){
sz[x]=1;
for(int i=head[x];i!=-1;i=edge[i].next){
if(edge[i].to==fa[x])continue;
fa[edge[i].to]=x,dis[edge[i].to]=dis[x]+edge[i].val,dep[edge[i].to]=dep[x]+1;
dfs1(edge[i].to);
sz[x]+=sz[edge[i].to];
if(sz[edge[i].to]>sz[son[x]])son[x]=edge[i].to;
}
}
void dfs2(int x){
dfn[x]=++tot,rev[tot]=x;if(!top[x])top[x]=x;
if(son[x])top[son[x]]=top[x],dfs2(son[x]);
for(int i=head[x];i!=-1;i=edge[i].next)if(edge[i].to!=fa[x]&&edge[i].to!=son[x])dfs2(edge[i].to);
}
int LCA(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);x=fa[top[x]];}if(dep[x]>dep[y])swap(x,y);return x;}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
namespace FS{//full section
ll mn[400100];
void build(int x,int l,int r){mn[x]=inf;if(l!=r)build(lson,l,mid),build(rson,mid+1,r);}
void modify(int x,int l,int r,int P,ll val){if(l>P||r<P)return;mn[x]=min(mn[x],val);if(l!=r)modify(lson,l,mid,P,val),modify(rson,mid+1,r,P,val);}
ll query(int x,int l,int r,int L,int R){if(l>R||r<L)return inf;if(L<=l&&r<=R)return mn[x];return min(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));}
}
namespace BS{//boundary situation
struct SegTree{ll b;int k;}seg[400100];
void build(int x,int l,int r){seg[x].k=0,seg[x].b=inf;if(l!=r)build(lson,l,mid),build(rson,mid+1,r);}
void modify(int x,int l,int r,int L,int R,int K,ll B){
if(l>R||r<L)return;
if(L<=l&&r<=R){
if(dis[rev[mid]]*K+B<dis[rev[mid]]*seg[x].k+seg[x].b)swap(seg[x].k,K),swap(seg[x].b,B);
if(dis[rev[l]]*K+B<dis[rev[l]]*seg[x].k+seg[x].b)modify(lson,l,mid,L,R,K,B);
if(dis[rev[r]]*K+B<dis[rev[r]]*seg[x].k+seg[x].b)modify(rson,mid+1,r,L,R,K,B);
return;
}
modify(lson,l,mid,L,R,K,B),modify(rson,mid+1,r,L,R,K,B);
}
ll query(int x,int l,int r,int P){
if(l>P||r<P)return inf;
ll ret=dis[rev[P]]*seg[x].k+seg[x].b;
if(l!=r)ret=min(ret,query(lson,l,mid,P)),ret=min(ret,query(rson,mid+1,r,P));
return ret;
}
}
void modify(int L,int R,int K,ll B){L=dfn[L],R=dfn[R],FS::modify(1,1,n,L,dis[rev[L]]*K+B),FS::modify(1,1,n,R,dis[rev[R]]*K+B),BS::modify(1,1,n,L,R,K,B);}
ll query(int L,int R){L=dfn[L],R=dfn[R];return min(FS::query(1,1,n,L,R),min(BS::query(1,1,n,L),BS::query(1,1,n,R)));}
void chain(int x,int y,int K,ll B){while(top[x]!=top[y])modify(top[x],x,K,B),x=fa[top[x]];modify(y,x,K,B);}
void pathmodify(int x,int y,int A,int B){int z=LCA(x,y);chain(x,z,-A,dis[x]*A+B),chain(y,z,A,(dis[x]-dis[z]*2)*A+B);}
ll pathquery(int x,int y){
ll ret=inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ret=min(ret,query(top[x],x)),x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);ret=min(ret,query(x,y));return ret;
}
int main(){
scanf("%d%d",&n,&m),memset(head,-1,sizeof(head));
for(int i=1,x,y,z;i<n;i++)scanf("%d%d%d",&x,&y,&z),ae(x,y,z);
dfs1(1),dfs2(1);
// for(int x=1;x<=n;x++)printf("FA:%d SN:%d SZ:%d DP:%d DS:%lld RV:%d DF:%d TP:%d\n",fa[x],son[x],sz[x],dep[x],dis[x],rev[x],dfn[x],top[x]);
FS::build(1,1,n),BS::build(1,1,n);
for(int i=1,x,y,a,b,tp;i<=m;i++){
scanf("%d%d%d",&tp,&x,&y);
if(tp==1)scanf("%d%d",&a,&b),pathmodify(x,y,a,b);
else printf("%lld\n",pathquery(x,y));
}
return 0;
}
```
## III.III.[CF932F Escape Through Leaf](https://www.luogu.com.cn/problem/CF932F)
明显DP式很容易写出；然后观察发现其就是子树中一堆函数 $y=kx+b$ 中对于某个 $x$ 的 $y$ 的最小值，于是线段树合并李超树就OK了。
需要注意的是，李超树因为每个节点都存了一条直线（相当于标记永久化），因此在合并点 $x$ 与 $y$ 时，要先合并 $x$ 与 $y$ 的儿子们，然后将 $y$ 上存的东西并到 $x$ 子树中。可以发现复杂度仍是 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[100100],b[100100],rt[100100],cnt,m;
vector<int>v[100100],u;
ll res[100100];
#define mid ((l+r)>>1)
struct Line{int k;ll b;Line(){k=0,b=0x3f3f3f3f3f3f3f3f;}Line(int K,ll B){k=K,b=B;}ll f(int x){return 1ll*k*x+b;}};
struct SegTree{int lson,rson;Line l;}seg[8001000];
void modify(int &x,int l,int r,Line L){
if(!x)x=++cnt;
if(seg[x].l.f(u[mid])>L.f(u[mid]))swap(L,seg[x].l);
if(seg[x].l.f(u[l])>L.f(u[l]))modify(seg[x].lson,l,mid,L);
if(seg[x].l.f(u[r])>L.f(u[r]))modify(seg[x].rson,mid+1,r,L);
}
void merge(int &x,int y,int l,int r){
if(!x){x=y;return;}if(!y)return;
if(l!=r)merge(seg[x].lson,seg[y].lson,l,mid),merge(seg[x].rson,seg[y].rson,mid+1,r);
modify(x,l,r,seg[y].l);
}
ll query(int x,int l,int r,int P){
if(l>P||r<P||!x)return 0x3f3f3f3f3f3f3f3f;
ll ret=seg[x].l.f(u[P]);
if(l!=r)ret=min(ret,min(query(seg[x].lson,l,mid,P),query(seg[x].rson,mid+1,r,P)));
return ret;
}
void dfs(int x,int fa){
for(auto y:v[x])if(y!=fa)dfs(y,x),merge(rt[x],rt[y],0,m-1);
if(v[x].size()==1&&x!=1)res[x]=0;
else res[x]=query(rt[x],0,m-1,a[x]);
modify(rt[x],0,m-1,Line(b[x],res[x]));
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),u.push_back(a[i]);
sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin());
for(int i=1;i<=n;i++)scanf("%d",&b[i]),a[i]=lower_bound(u.begin(),u.end(),a[i])-u.begin();
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
dfs(1,0);
for(int i=1;i<=n;i++)printf("%lld ",res[i]);puts("");
return 0;
}
```
## III.IV.[[HDU3842][WF2011]Machine Works](http://acm.hdu.edu.cn/showproblem.php?pid=3842)
我们设 $f_i$ 表示第 $i$ 台机器被购买时，所剩最多钱数。则
$$f_i=\max\limits_{d_j<d_i}\Big\{f_j+(d_i-d_j-1)g_j+r_j-p_i\Big\}$$
其可被拆作仅与 $j$ 相关的常数项、仅与 $i$ 相关的最后统一加上的项，以及与 $i,j$ 均有关的项。
这一项是 $-d_ig_j$，对于不同的 $i$ 来说，可看作是直线 $-g_jx+\text{常数项}$。
于是直接李超树维护即可。
时间复杂度 $O(n\log^2n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=-0x3f3f3f3f3f3f3f3f;
vector<int>v[100100],u;
int n,c,m,q,d[100100],p[100100],r[100100],g[100100],mx[400100],TT;
ll f[100100],res;
ll calc(int x,int y){
if(!x)return inf;
return f[x]+1ll*(u[d[y]-1]-u[d[x]-1]-1)*g[x]+r[x]-p[y];
}
#define lson x<<1
#define rson x<<1|1
#define mid ((l+r)>>1)
void modify(int x,int l,int r,int y){
if(r<=d[y])return;
if(l>d[y]){
if(calc(y,v[mid][0])>calc(mx[x],v[mid][0]))swap(y,mx[x]);
if(calc(y,v[l][0])>calc(mx[x],v[l][0]))modify(lson,l,mid,y);
if(calc(y,v[r][0])>calc(mx[x],v[r][0]))modify(rson,mid+1,r,y);
return;
}
modify(lson,l,mid,y),modify(rson,mid+1,r,y);
}
ll query(int x,int l,int r,int P){
if(l>d[P]||r<d[P])return inf;
// printf("%d:[%d,%d]:%d:%d\n",x,l,r,P,mx[x]);
ll ret=calc(mx[x],P);
if(l!=r)ret=max(ret,max(query(lson,l,mid,P),query(rson,mid+1,r,P)));
return ret;
}
void reset(int x,int l,int r){mx[x]=0;if(l!=r)reset(lson,l,mid),reset(rson,mid+1,r);}
int main(){
while(true){
scanf("%d%d%d",&n,&c,&q),res=c;
if(!n&&!c&&!q)break;
for(int i=1;i<=n;i++)scanf("%d%d%d%d",&d[i],&p[i],&r[i],&g[i]),u.push_back(d[i]);
sort(u.begin(),u.end()),u.resize(m=unique(u.begin(),u.end())-u.begin());
for(int i=1;i<=n;i++)v[d[i]=lower_bound(u.begin(),u.end(),d[i])-u.begin()+1].push_back(i);
// for(int i=1;i<=n;i++)printf("%d ",d[i]);puts("");
for(int i=1;i<=m;i++){
for(auto j:v[i])f[j]=max(0ll+c-p[j],query(1,1,m,j));
for(auto j:v[i])if(f[j]>=0)modify(1,1,m,j),res=max(res,f[j]+1ll*(q-u[d[j]-1])*g[j]+r[j]);
}
printf("Case %d: %lld\n",++TT,res);
u.clear();
reset(1,1,m);
for(int i=1;i<=m;i++)v[i].clear();
}
return 0;
}
```
# IV.CDQ分治
## IV.I.[[SDOI2011]拦截导弹](https://www.luogu.com.cn/problem/P2487)
我当初为什么要用CDQ分治而不是树套树开这题……
明显三维偏序。然后一个点的可能性就是前缀路径数乘以后缀路径数除以总路径数。
CDQ分治有一大坨的细节需要处理！
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
int n,m;
struct tad{
int len;
ld ways;
tad(){len=0,ways=0;}
tad(int L,ld W){len=L,ways=W;}
friend tad operator+(const tad&u,const tad&v){
tad w;
w.len=max(u.len,v.len);
if(w.len==u.len)w.ways+=u.ways;
if(w.len==v.len)w.ways+=v.ways;
return w;
}
}t[50100],res;
void ADD(int x,tad y){while(x)t[x]=t[x]+y,x-=x&-x;}
tad SUM(int x){tad ret;while(x<=m)ret=ret+t[x],x+=x&-x;ret.len++;return ret;}
void ERA(int x){while(x)t[x]=tad(),x-=x&-x;}
struct dat{int x,y,z;}p[50100],q[50100];
bool cmp1(dat&u,dat&v){return u.x<v.x;}
bool cmp2(dat&u,dat&v){return u.y>v.y;}
void CDQ(int l,int r,tad *F){
if(l==r)return;
int mid=(l+r)>>1;
CDQ(l,mid,F);
for(int i=l;i<=r;i++)q[i]=p[i];
sort(q+l,q+mid+1,cmp2),sort(q+mid+1,q+r+1,cmp2);
for(int i=l,j=mid+1;j<=r;j++){
while(i<=mid&&q[i].y>=q[j].y)ADD(q[i].z,F[q[i].x]),i++;
F[q[j].x]=F[q[j].x]+SUM(q[j].z);
}
for(int i=l;i<=mid;i++)ERA(q[i].z);
CDQ(mid+1,r,F);
}
vector<int>v;
tad f[50100],g[50100];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d",&p[i].y,&p[i].z),v.push_back(p[i].z),p[i].x=i,f[i]=g[i]=tad(1,1);
sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)p[i].z=lower_bound(v.begin(),v.end(),p[i].z)-v.begin()+1;
CDQ(1,n,f);
for(int i=1;i<=n;i++)p[i].x=n-p[i].x+1,p[i].y=-p[i].y,p[i].z=m-p[i].z+1;
sort(p+1,p+n+1,cmp1);
// for(int i=1;i<=n;i++)printf("(%d,%d,%d)",p[i].x,p[i].y,p[i].z);puts("");
CDQ(1,n,g);
reverse(g+1,g+n+1);
// for(int i=1;i<=n;i++)printf("(%d,%Lf)",f[i].len,f[i].ways);puts("");
// for(int i=1;i<=n;i++)printf("(%d,%Lf)",g[i].len,g[i].ways);puts("");
for(int i=1;i<=n;i++)res=res+f[i];
printf("%d\n",res.len);
for(int i=1;i<=n;i++)if(f[i].len+g[i].len-1==res.len)printf("%Lf ",f[i].ways*g[i].ways/res.ways);else printf("0 ");
return 0;
}
```
## IV.II.[[HNOI2010]城市建设](https://www.luogu.com.cn/problem/P3206)
实际上这题不算狭义上的CDQ分治（先计算左边，再计算左边对右边的贡献，最后计算右边），更像是线段树分治的变种，但是既然大家都认为这就是CDQ那就算是罢……
------
考虑分治计算。当我们考虑一个区间 $[l,r]$ 时，我们会将所有边分为两类：区间 $[l,r]$ 内操作涉及到的边，称作**动态边**；未涉及到的边，称作**静态边**。显然，对于 $[l,r]$ 的子集来说，静态边只会增加不会减少，因此我们考虑在 $[l,r]$ 处就着手缩减静态边集中不需要的部分。
我们发现，对于 $[l,r]$ 中的动态边来说，就算它们全连上也不一定会使得整张图联通，因而连上所有动态边后剩余的连通块间就必然要使用静态边连接。于是这部分的静态边就可以直接跑个MST来联通这些剩余的连通块。显然，此时MST上连出的边，在子区间里是一定会被保留的，故可以缩点。
于是总结一下此部分的操作：
1. 对动态边缩点
2. 对静态边求MST
3. 撤销上述所有操作直到1执行之前，然后连回2中求出的MST上的边。（明显，此部分要使用可撤销冰茶姬）
于是我们现在便率先压缩了点数，并删除了部分静态边。
在上述操作之后，我们又发现一点可乘之机：有部分静态边是不可能出现在最终的MST上的，因为此时它们已经可以被其它静态边替代掉了。
于是我们要再跑一遍静态边的MST，并丢弃掉所有不在MST上的静态边。
显然，一个区间中动态边数量是区间长度级别的；故第一次压缩点数后所剩余的点数也是区间长度级别的；故第二次压缩边数后所剩余的边数也是区间长度级别的；于是我们发现经历上述操作后，区间动态边、静态边数均是区间长度级别的；于是复杂度为分治的一个 $\log$ 乘以（MST的一个 $\log$ 以及可撤销冰茶姬的一个 $\log$），为 $n\log^2n$。
需要注意的是，在递归到区间长度为 $1$ 时，就直接把修改操作执行，然后暴力跑个MST就行了。
（还有一种解法是非常trivial的线段树分治套LCT，虽然也是 $O(n\log^2n)$ 但是有着众所周知的大常数因此跑不过去，虽然如果省选时遇到这道题我肯定就暴力上LCT了，因为CDQ分治的解法太太太恶心了）
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,q,id[50010],val[50010],dsu[20010],sz[20010];
struct dat{int u,v,su,sv;dat(int U,int V,int SU,int SV){u=U,v=V,su=SU,sv=SV;}};
stack<dat>s;
void undo(){dsu[s.top().u]=s.top().u,dsu[s.top().v]=s.top().v,sz[s.top().u]=s.top().su,sz[s.top().v]=s.top().sv,s.pop();}
int find(int x){return dsu[x]==x?x:find(dsu[x]);}
struct EDGE{
int x,y,z;
bool merge(){
int X=find(x),Y=find(y);if(X==Y)return false;
if(sz[X]>sz[Y])swap(X,Y);
s.push(dat(X,Y,sz[X],sz[Y])),dsu[X]=Y,sz[Y]+=sz[X];
return true;
}
}e[50010];
ll res,ans[50010];
vector<int>stl,mov;//still edges and movable edges
bool nst[50010];//if the edge is non-still
bool cmp(int x,int y){return e[x].z<e[y].z;}
void solve(int l,int r){
ll RES=res;vector<int>STL=stl,MOV=mov;int SZ=s.size();//those are the old information
// printf("BEF:[%d,%d]\n",l,r);printf("STL:");for(auto i:stl)printf("%d ",i);puts("");printf("MOV:");for(auto i:mov)printf("%d ",i);puts("");
for(int i=l;i<=r;i++)nst[id[i]]=true;
vector<int>tmp;
for(auto i:mov)if(nst[i])tmp.push_back(i);else stl.push_back(i);//separate those once-movable edges into still-movable edges and newly-still edges
for(int i=l;i<=r;i++)nst[id[i]]=false;
mov=tmp;
// printf("MID:[%d,%d]\n",l,r);printf("STL:");for(auto i:stl)printf("%d ",i);puts("");printf("MOV:");for(auto i:mov)printf("%d ",i);puts("");
// for(int i=1;i<=n;i++)printf("%d ",find(i));puts("");
int S=s.size();
for(auto i:mov)e[i].merge();//merge movable edges, to find those must-add edges
tmp.clear();vector<int>pmt;//pmt holds the must-add edges.
sort(stl.begin(),stl.end(),cmp);for(auto i:stl)if(e[i].merge())res+=e[i].z,pmt.push_back(i);else tmp.push_back(i);
stl=tmp;while(s.size()>S)undo();
for(auto i:pmt)e[i].merge();//now must-add edges have all been merged.
// for(int i=1;i<=n;i++)printf("%d ",find(i));puts("");
tmp.clear(),S=s.size();
for(auto i:stl)if(e[i].merge())tmp.push_back(i);
while(s.size()>S)undo();stl=tmp;//now stl holds the minimum-spaning-forest,of those current-still edges
// printf("AFT:[%d,%d]\n",l,r);printf("STL:");for(auto i:stl)printf("%d ",i);puts("");printf("MOV:");for(auto i:mov)printf("%d ",i);puts("");
if(l==r){
e[id[l]].z=val[l],stl.push_back(id[l]);
sort(stl.begin(),stl.end(),cmp);for(auto i:stl)if(e[i].merge())res+=e[i].z;
ans[l]=res;
}else{int mid=(l+r)>>1;solve(l,mid),solve(mid+1,r);}
while(s.size()>SZ)undo();res=RES,stl=STL,mov=MOV;
}
int main(){
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)dsu[i]=i,sz[i]=1;
for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z),mov.push_back(i);//initially all edges are considered movable
for(int i=1;i<=q;i++)scanf("%d%d",&id[i],&val[i]);
solve(1,q);
for(int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}
```
## IV.III.[[国家集训队]数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)
虽然这里这题的写法是CDQ但是我还是要大声喊出：树套树yyds！
首先，众所周知地，我们可以对于每个位置记录其颜色上一次出现的地方，记作 $las_i$，则我们需要知道的就是 $[l,r]$ 中 $las_i<l$ 的总数。
众所周知地，这是二维数点问题。现在有了修改操作，需要保证时间顺序，因此变成了大家都喜欢的三维数点问题。
具体操作很简单：因为观察到一次修改最多改变 $3$ 个位置的 $las$ 值，放到二维数点的平面上就是 $6$ 次修改，于是预处理这六次修改的样式，然后CDQ分治时计算左侧的修改对右侧询问的影响就行了。可以采用树状数组简单处理。
但是CDQ分治也有其优点，就是空间复杂度是 $O(n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[150010],lim,las[150010],res[150010],t[150010];
vector<int>v;
struct node{
int tp,a,b;
node(){}
node(int T,int A,int B){tp=T,a=A,b=B;}
friend bool operator<(const node&x,const node&y){return x.a==y.a?!x.tp>!y.tp:x.a<y.a;}
}q[150010];
char str[10];
set<int>s[300010];
void ADD(int x,int y){while(x<=n)t[x]+=y,x+=x&-x;}
int SUM(int x){int ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
vector<node>u,w[150010];
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)if(!q[i].tp)for(auto j:w[i])u.push_back(j);
for(int i=mid+1;i<=r;i++)if(q[i].tp)for(auto j:w[i])u.push_back(j);
sort(u.begin(),u.end());
for(auto i:u){
if(!i.tp){
if(i.b>0)ADD(i.b,1);
else ADD(-i.b,-1);
}else{
if(i.tp>0)res[i.tp]+=SUM(i.b);
else res[-i.tp]-=SUM(i.b);
}
}
u.clear();
for(auto i:u)if(!i.tp){
if(i.b>0)ADD(i.b,-1);
else ADD(-i.b,1);
}
CDQ(l,mid),CDQ(mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
for(int i=1;i<=m;i++){
scanf("%s%d%d",str,&q[i].a,&q[i].b),q[i].tp=(str[0]=='Q');
if(str[0]=='R')v.push_back(q[i].b);
}
sort(v.begin(),v.end()),v.resize(lim=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)s[a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1].insert(i);
for(int i=1;i<=m;i++)if(!q[i].tp)q[i].b=lower_bound(v.begin(),v.end(),q[i].b)-v.begin()+1;
for(int i=1;i<=n;i++){
auto tmp=s[a[i]].lower_bound(i);
if(tmp!=s[a[i]].begin())las[i]=1+*--tmp;
else las[i]=1;
}
for(int i=1;i<=m;i++){
if(!q[i].tp)continue;
u.emplace_back(-i,q[i].a-1,q[i].a),u.emplace_back(i,q[i].b,q[i].a);
w[i].emplace_back(-i,q[i].a-1,q[i].a),w[i].emplace_back(i,q[i].b,q[i].a);
}
sort(u.begin(),u.end());
for(int i=0,j=1;i<u.size();i++){
while(j<=u[i].a)ADD(las[j++],1);
if(u[i].tp>0)res[u[i].tp]+=SUM(u[i].b);else res[-u[i].tp]-=SUM(u[i].b);
}
u.clear(),memset(t,0,sizeof(t));
for(int i=1;i<=m;i++){
if(q[i].tp)continue;
int P=q[i].a,C=q[i].b;
if(C==a[P])continue;
w[i].emplace_back(0,P,-las[P]);
s[a[P]].erase(P);
auto tmp=s[a[P]].lower_bound(P);
if(tmp!=s[a[P]].end())w[i].emplace_back(0,*tmp,-las[*tmp]),w[i].emplace_back(0,*tmp,las[*tmp]=las[P]);
tmp=s[C].lower_bound(P);
if(tmp!=s[C].end()){
w[i].emplace_back(0,P,las[P]=las[*tmp]);
w[i].emplace_back(0,*tmp,-las[*tmp]);
w[i].emplace_back(0,*tmp,las[*tmp]=P+1);
}else if(tmp!=s[C].begin())w[i].emplace_back(0,P,las[P]=1+*--tmp);
else w[i].emplace_back(0,P,las[P]=1);
a[P]=C;
s[C].insert(P);
}
CDQ(1,m);
for(int i=1;i<=m;i++)if(q[i].tp)printf("%d\n",res[i]);
return 0;
}
```
## IV.IV.[[Ynoi2016] 镜中的昆虫](https://www.luogu.com.cn/problem/P4690)
没错，这里就是CDQ分治 $O(n)$ 的优势所在了——本题似乎卡掉了空间复杂度为 $O(n\log^2n)$ 的树套树。
~~但这不妨碍我继续说：树套树yyds~~
首先，这里有一个结论：长度为 $n$ 的序列，修改 $m$ 次，$las$ 数组变化的次数是 $O(n+m)$ 的。
证明：
我们不妨将其看成初始有一个长度为 $n$ 的全相同序列，之后先进行 $n$ 次单点修改，再进行 $m$ 次区间修改，也就是说总共进行 $n+m$ 次修改。
考虑一次修改 $[l,r]$。显然，此次修改相当于把 $las_l$ 设成一个可以被求出的值，然后将 $i\in(l,r]$ 的 $las_i$ 设作 $i-1$。
同时，其会影响 $[l,r]$ 中出现过的所有颜色，再加上区间修改的目标颜色，这所有颜色的各一个位置——但是这些位置必定是以前某个 $[l,r]$ 的 $l$ 位置，或者是被某次修改打断形成的新区间。
实际上，这里可以结合珂朵莉树的思想理解——珂朵莉树中存了连续的取值相同的区间，而此种区间除了开头的一个数的 $las$ 值外，其余 $las$ 都是 $i-1$。
一次修改，会产生 $O(1)$ 个新区间，并推平一些旧区间。但是旧区间除了区间开头的元素，其余位置都不需要改变。因为一个区间最多产生一次并被推平一次，所以总数是 $O(n+m)$ 级别的。
这时直接用珂朵莉树维护 $las$ 值。要开一棵大珂朵莉树，同时对每种颜色各开一棵小珂朵莉树。
时间复杂度 $O(n\log^2n)$。
~~珂朵莉树太难写了，一坨坨 `set` 看得人头晕~~
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010],las[100010],res[100010],t[100010],buc[200100];
vector<int>v;
struct node{
int tp,a,b;
node(){}
node(int T,int A,int B){tp=T,a=A,b=B;}
friend bool operator<(const node&x,const node&y){return x.a==y.a?!x.tp>!y.tp:x.a<y.a;}
};
void ADD(int x,int y){while(x<=n)t[x]+=y,x+=x&-x;}
int SUM(int x){int ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
vector<node>u,w[100010];
int L[100100],R[100100],C[100100],tp[100100];
set<pair<int,int> >s[200010];
struct dat{
int l,r,c;
dat(int L,int R,int C){l=L,r=R,c=C;}
friend bool operator<(const dat&u,const dat&v){return u.l<v.l;}
};
set<dat>S;
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)if(!tp[i])for(auto j:w[i])u.push_back(j);
for(int i=mid+1;i<=r;i++)if(tp[i])for(auto j:w[i])u.push_back(j);
sort(u.begin(),u.end());
for(auto i:u){
if(!i.tp){
if(i.b>0)ADD(i.b,1);
else ADD(-i.b,-1);
}else{
if(i.tp>0)res[i.tp]+=SUM(i.b);
else res[-i.tp]-=SUM(i.b);
}
}
u.clear();
for(auto i:u)if(!i.tp){
if(i.b>0)ADD(i.b,-1);
else ADD(-i.b,1);
}
CDQ(l,mid),CDQ(mid+1,r);
}
#define CLAS(x,y) w[i].emplace_back(0,x,-las[x]),w[i].emplace_back(0,x,las[x]=y)
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&tp[i],&L[i],&R[i]),tp[i]=(tp[i]==2);
if(!tp[i])scanf("%d",&C[i]),v.push_back(C[i]);
}
sort(v.begin(),v.end()),v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
for(int i=1;i<=m;i++)if(!tp[i])C[i]=lower_bound(v.begin(),v.end(),C[i])-v.begin()+1;
for(int i=1;i<=n;i++)las[i]=buc[a[i]]+1,buc[a[i]]=i;
for(int i=1;i<=m;i++){
if(!tp[i])continue;
u.emplace_back(-i,L[i]-1,L[i]),u.emplace_back(i,R[i],L[i]);
w[i].emplace_back(-i,L[i]-1,L[i]),w[i].emplace_back(i,R[i],L[i]);
}
sort(u.begin(),u.end());
for(int i=0,j=1;i<u.size();i++){
while(j<=u[i].a)ADD(las[j++],1);
if(u[i].tp>0)res[u[i].tp]+=SUM(u[i].b);else res[-u[i].tp]-=SUM(u[i].b);
}
u.clear(),memset(t,0,sizeof(t));
for(int i=1,j=1;i<=n;i=j){
while(j<=n&&a[i]==a[j])j++;
S.insert(dat(i,j-1,a[i]));
s[a[i]].insert(make_pair(i,j-1));
}
for(int i=1;i<=m;i++){
if(tp[i])continue;
auto p=S.upper_bound(dat(L[i],L[i],L[i])),q=S.upper_bound(dat(R[i],R[i],R[i]));
auto r=p--;
for(;r!=q;++r)CLAS(r->l,r->l);
for(r=p;r!=q;++r)s[r->c].erase(make_pair(r->l,r->r));
if(p->l<L[i])s[p->c].insert(make_pair(p->l,L[i]-1));
r=q;--r;
if(r->r>R[i])s[r->c].insert(make_pair(R[i]+1,r->r));
s[C[i]].insert(make_pair(L[i],R[i]));
auto o=s[C[i]].lower_bound(make_pair(L[i],0));
if(o!=s[C[i]].begin())--o,CLAS(L[i],o->second+1);else CLAS(L[i],1);
for(r=p;r!=q;++r){
o=s[r->c].upper_bound(make_pair(R[i],0x3f3f3f3f));
if(o==s[r->c].end())continue;
int tmp=o->first;
if(o!=s[r->c].begin())--o,CLAS(tmp,o->second+1);else CLAS(tmp,1);
}
o=s[C[i]].upper_bound(make_pair(R[i],0x3f3f3f3f));
if(o!=s[C[i]].end())CLAS(o->first,R[i]+1);
int LL=p->l,LC=p->c;
r=q;--r;int RR=r->r,RC=r->c;
for(r=p;r!=q;r=S.erase(r));
S.insert(dat(L[i],R[i],C[i]));
if(LL!=L[i])S.insert(dat(LL,L[i]-1,LC));
if(RR!=R[i])S.insert(dat(R[i]+1,RR,RC));
// for(auto k:w[i])printf("[%d,%d]",k.a,k.b);puts("");
// for(auto k:S)printf("(%d,%d,%d)",k.l,k.r,k.c);puts("");
}
CDQ(1,m);
for(int i=1;i<=m;i++)if(tp[i])printf("%d\n",res[i]);
return 0;
}
```
## IV.V.[[DBOI2019]德丽莎世界第一可爱](https://www.luogu.com.cn/problem/P5621)
~~事四维偏序模板~~
二维偏序我们用BIT，三维偏序我们用CDQ套BIT，四维偏序，可以CDQ套~~树套树~~CDQ套BIT。
什么意思？
我们排序排掉第一维。
然后，在第二维上CDQ：当我们要计算 $[l,mid]$ 对 $[mid+1,r]$ 的贡献时，发现其有如下几条限制：
贡献的物品来自 $[l,mid]$，收到贡献的物品来自 $[mid+1,r]$；二、三、四维满足偏序关系。
于是我们继续CDQ，只不过，在内层的CDQ时，我们只将外层CDQ中 $[l,mid]$ 中物品加入BIT，只有 $[mid+1,r]$ 中物品能从BIT更新。
这就意味着我们得在每个物品额外打上一个标记，用来表示其是否在 $[l,mid]$ 中。
同时，有一些需要注意的地方：
1. CDQ分治时不能乱动数组，排序后要么复原，要么额外拷贝一份排序。
2. 排序时，比如我们以排第三维为例，光按第三维排不够，要继续按第四维，然后是一维、二维排。
3. 注意相同的元素，以及答案是负数的情形。
~~可能会debug很久很久~~
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=0xc0c0c0c0c0c0c0c0;
int n,m;
ll res=inf,f[50100];
struct node{
ll a,b,c,d,e;
int id;
bool fir;
node(){}
node(ll A,ll B,ll C,ll D){a=A,b=B,c=C,d=D;}
friend bool operator==(const node&u,const node&v){return u.a==v.a&&u.b==v.b&&u.c==v.c&&u.d==v.d;}
void print(){printf("(%d,%d,%d,%d,%d):%d-%d\n",a,b,c,d,e,f[id],fir);}
}p[50100],q[50100],o[50100];
bool cmpa(node&x,node&y){
if(x.a!=y.a)return x.a<y.a;
if(x.b!=y.b)return x.b<y.b;
if(x.c!=y.c)return x.c<y.c;
if(x.d!=y.d)return x.d<y.d;
return x.e>y.e;
}
bool cmpb(node&x,node&y){
if(x.b!=y.b)return x.b<y.b;
if(x.c!=y.c)return x.c<y.c;
if(x.d!=y.d)return x.d<y.d;
return x.a<y.a;
}
bool cmpc(node&x,node&y){
if(x.c!=y.c)return x.c<y.c;
if(x.d!=y.d)return x.d<y.d;
if(x.a!=y.a)return x.a<y.a;
return x.b<y.b;
}
vector<int>v;
ll t[50100];
void ADD(int x,ll y){while(x<=m)t[x]=max(t[x],y),x+=x&-x;}
ll SUM(int x){ll ret=inf;while(x)ret=max(ret,t[x]),x-=x&-x;return ret;}
void ERA(int x){while(x<=m)t[x]=inf,x+=x&-x;}
void CDQ2(int l,int r){
// printf("2:[%d,%d]\n",l,r);
if(l==r)return;
int mid=(l+r)>>1;
CDQ2(l,mid);
for(int i=l;i<=r;i++)q[i]=o[i];
sort(q+l,q+mid+1,cmpc),sort(q+mid+1,q+r+1,cmpc);
// printf("C:");for(int i=l;i<=r;i++)printf("%d ",q[i].id);puts("");
for(int i=l,j=mid+1;j<=r;j++){
for(;i<=mid&&q[i].c<=q[j].c;i++)if(q[i].fir)ADD(q[i].d,f[q[i].id]);
if(!q[j].fir)f[q[j].id]=max(f[q[j].id],q[j].e+SUM(q[j].d));
}
for(int i=l;i<=mid;i++)if(q[i].fir)ERA(q[i].d);
CDQ2(mid+1,r);
}
void CDQ1(int l,int r){
// printf("1:[%d,%d]\n",l,r);
if(l==r){res=max(res,f[p[l].id]);return;}
int mid=(l+r)>>1;
CDQ1(l,mid);
for(int i=l;i<=r;i++)o[i]=p[i];
for(int i=l;i<=mid;i++)o[i].fir=true;
sort(o+l,o+r+1,cmpb);
// printf("B:");for(int i=l;i<=r;i++)printf("%d ",o[i].id);puts("");
CDQ2(l,r);
CDQ1(mid+1,r);
}
int main(){
scanf("%d",&m);
for(int i=1;i<=m;i++)scanf("%lld%lld%lld%lld%lld",&p[i].a,&p[i].b,&p[i].c,&p[i].d,&p[i].e),v.push_back(p[i].d);
sort(p+1,p+m+1,cmpa),n=1;
for(int i=2;i<=m;i++)if(p[n]==p[i])p[n].e+=max(p[i].e,0ll);else p[++n]=p[i];
sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)p[i].id=i,f[i]=p[i].e,p[i].fir=false,p[i].d=lower_bound(v.begin(),v.end(),p[i].d)-v.begin()+1;
memset(t,0xc0,sizeof(t));
// for(int i=1;i<=n;i++)p[i].print();
// printf("A:");for(int i=1;i<=n;i++)printf("%d ",p[i].id);puts("");
CDQ1(1,n);
printf("%lld\n",res);
return 0;
}
```
## IV.VI.[寻找宝藏](https://www.luogu.com.cn/problem/P4849)
又是四维偏序板子。只不过是打一遍再熟悉一下代码罢了。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m;
typedef long long ll;
struct dat{
ll val;
int ways;
dat(){val=ways=0;}
dat(ll V,int W){val=V,ways=W;}
friend dat operator+(const dat&u,const dat&v){
dat w;
w.val=max(u.val,v.val);
if(w.val==u.val)w.ways+=u.ways;
if(w.val==v.val)w.ways+=v.ways;
w.ways%=mod;
return w;
}
}f[80100],t[80100],res;
void ADD(int x,dat y){while(x<=n)t[x]=t[x]+y,x+=x&-x;}
dat SUM(int x){dat ret;while(x)ret=ret+t[x],x-=x&-x;return ret;}
void ERA(int x){while(x<=n)t[x]=dat(),x+=x&-x;}
struct node{
int a,b,c,d,id;
ll e;
bool fir;
friend bool operator==(const node&x,const node&y){return x.a==y.a&&x.b==y.b&&x.c==y.c&&x.d==y.d;}
}o[80100],p[80100],q[80100];
bool cmpa(const node&x,const node&y){
if(x.a!=y.a)return x.a<y.a;
if(x.b!=y.b)return x.b<y.b;
if(x.c!=y.c)return x.c<y.c;
return x.d<y.d;
}
bool cmpb(const node&x,const node&y){
if(x.b!=y.b)return x.b<y.b;
if(x.c!=y.c)return x.c<y.c;
if(x.d!=y.d)return x.d<y.d;
return x.a<y.a;
}
bool cmpc(const node&x,const node&y){
if(x.c!=y.c)return x.c<y.c;
if(x.d!=y.d)return x.d<y.d;
if(x.a!=y.a)return x.a<y.a;
return x.b<y.b;
}
void CDQ2(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
CDQ2(l,mid);
for(int i=l;i<=r;i++)q[i]=p[i];
sort(q+l,q+mid+1,cmpc),sort(q+mid+1,q+r+1,cmpc);
for(int i=l,j=mid+1;j<=r;j++){
for(;i<=mid&&q[i].c<=q[j].c;i++)if(q[i].fir)ADD(q[i].d,f[q[i].id]);
if(!q[j].fir){
dat tmp=SUM(q[j].d);tmp.val+=q[j].e;
f[q[j].id]=f[q[j].id]+tmp;
}
}
for(int i=l;i<=mid;i++)if(q[i].fir)ERA(q[i].d);
CDQ2(mid+1,r);
}
void CDQ1(int l,int r){
if(l==r){res=res+f[o[l].id];return;}
int mid=(l+r)>>1;
CDQ1(l,mid);
for(int i=l;i<=r;i++)p[i]=o[i];
for(int i=l;i<=mid;i++)p[i].fir=true;
sort(p+l,p+r+1,cmpb);
CDQ2(l,r);
CDQ1(mid+1,r);
}
vector<int>v;
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d%d%d%lld",&o[i].a,&o[i].b,&o[i].c,&o[i].d,&o[i].e);
sort(o+1,o+n+1,cmpa),m=1;
for(int i=2;i<=n;i++)if(o[m]==o[i])o[m].e+=o[i].e;else o[++m]=o[i];
n=m;
for(int i=1;i<=n;i++)v.push_back(o[i].d);
sort(v.begin(),v.end()),v.resize(m=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)o[i].d=lower_bound(v.begin(),v.end(),o[i].d)-v.begin()+1,f[i]=dat(o[i].e,1),o[i].id=i;
CDQ1(1,n);
printf("%lld\n%d\n",res.val,res.ways);
return 0;
}
```
# V.整体二分
## V.I.[[POI2011]MET-Meteors](https://www.luogu.com.cn/problem/P3527)
套上整体二分，然后用BIT统计区间里每个国家收到多少陨石就行了。
听说有人还有用线段树上二分之类奇怪的东西，但是真的没有必要。
时间复杂度 $O(n\log^2n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[300100],q,L[300100],R[300100],V[300100],p[300100],res[300100];
bool ok[300100];
vector<int>v[300100];
ll t[300100];
void ADD(int x,int y){while(x<=m)t[x]+=y,x+=x&-x;}
ll SUM(int x){ll ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
void solve(int l,int r,int ll,int rr){
if(l==r){for(int i=ll;i<=rr;i++)res[p[i]]=l;return;}
// printf("[%d,%d]:",l,r);for(int i=ll;i<=rr;i++)printf("%d ",p[i]);puts("");
if(ll>rr)return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)if(L[i]<=R[i])ADD(L[i],V[i]),ADD(R[i]+1,-V[i]);else ADD(1,V[i]),ADD(R[i]+1,-V[i]),ADD(L[i],V[i]);
for(int i=ll;i<=rr;i++){
long long sum=0;
for(auto j:v[p[i]]){
sum+=SUM(j);
if(sum>=a[p[i]])break;
}
// printf("%d\n",sum);
if(sum>=a[p[i]])ok[p[i]]=true;else ok[p[i]]=false,a[p[i]]-=sum;
}
for(int i=l;i<=mid;i++)if(L[i]<=R[i])ADD(L[i],-V[i]),ADD(R[i]+1,V[i]);else ADD(1,-V[i]),ADD(R[i]+1,V[i]),ADD(L[i],-V[i]);
sort(p+ll,p+rr+1,[](int u,int v){return ok[u]>ok[v];});
int MID=ll-1;while(MID<rr&&ok[p[MID+1]])MID++;
for(int i=ll;i<=rr;i++)ok[p[i]]=false;
solve(l,mid,ll,MID),solve(mid+1,r,MID+1,rr);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x;i<=m;i++)scanf("%d",&x),v[x].push_back(i);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
scanf("%d",&q);
for(int i=1;i<=q;i++)scanf("%d%d%d",&L[i],&R[i],&V[i]);
q++,L[q]=1,R[q]=n,V[q]=0x3f3f3f3f;
for(int i=1;i<=n;i++)p[i]=i;
solve(1,q,1,n);
for(int i=1;i<=n;i++)if(res[i]==q)puts("NIE");else printf("%d\n",res[i]);
return 0;
}
```
## V.II.[[国家集训]矩阵乘法](https://www.luogu.com.cn/problem/P1527)
整体二分，然后套上二维BIT统计就行了。
需要注意的是整体二分时，要注意哪里是“编号”，哪里不是！（放在代码中就是哪里的东西外面要套上一层 `p[]`）
时间复杂度 $O(m\log m\log^2n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,g[510][510],X1[60100],Y1[60100],X2[60100],Y2[60100],K[60100],p[60100],res[60100],t[510][510];
vector<int>u;
vector<pair<int,int> >v[251000];
void ADD(int x,int y,int z){for(int i=x;i<=n;i+=i&-i)for(int j=y;j<=n;j+=j&-j)t[i][j]+=z;}
int SUM(int x,int y){int ret=0;for(int i=x;i;i-=i&-i)for(int j=y;j;j-=j&-j)ret+=t[i][j];return ret;}
bool ok[60100];
void solve(int l,int r,int L,int R){
if(l==r){for(int i=L;i<=R;i++)res[p[i]]=u[l-1];return;}
if(L>R)return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)for(auto j:v[i])ADD(j.first,j.second,1);
for(int i=L;i<=R;i++){
int sum=SUM(X2[p[i]],Y2[p[i]])-SUM(X1[p[i]],Y2[p[i]])-SUM(X2[p[i]],Y1[p[i]])+SUM(X1[p[i]],Y1[p[i]]);
if(sum>=K[p[i]])ok[p[i]]=true;else K[p[i]]-=sum,ok[p[i]]=false;
}
for(int i=l;i<=mid;i++)for(auto j:v[i])ADD(j.first,j.second,-1);
sort(p+L,p+R+1,[](int x,int y){return ok[x]>ok[y];});
int MID=L-1;while(MID<R&&ok[p[MID+1]])MID++;
solve(l,mid,L,MID),solve(mid+1,r,MID+1,R);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&g[i][j]),u.push_back(g[i][j]);
sort(u.begin(),u.end()),u.resize(unique(u.begin(),u.end())-u.begin());
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)v[g[i][j]=lower_bound(u.begin(),u.end(),g[i][j])-u.begin()+1].push_back(make_pair(i,j));
for(int i=1;i<=m;i++)scanf("%d%d%d%d%d",&X1[i],&Y1[i],&X2[i],&Y2[i],&K[i]),p[i]=i,X1[i]--,Y1[i]--;
solve(1,u.size(),1,m);
for(int i=1;i<=m;i++)printf("%d\n",res[i]);
return 0;
}
```
## V.III.[[CTSC2018]混合果汁](https://www.luogu.com.cn/problem/P4602)
二话不说先套个整体二分。
但是这题整体二分与先前两道题有所区别——前面两道题，当二分到区间 $[l,r]$ 时，只需管 $[l,r]$ 中的元素就行了，对于 $mid$ 不合法的询问直接减去这一段的询问的结果就行了；
但是，本题就不一样了：随着美味度下界的不断降低，我们可能会放弃贵但美味的饮料，转而选择便宜但不美味的饮料。这就意味着上面的做法不太行。
但是，我们是有办法的：仿照CDQ分治的思想，当处理区间 $[l,r]$ 结束后，我们首先处理 $[mid,r]$，等到遍历到叶子节点时将其代表的元素加入BIT，等 $[mid,r]$ 全数处理完成后再处理 $[l,mid]$。这样子，在处理任何 $[l,r]$ 时，$[r+1,n]$ 便已经在BIT里了。
至于这个BIT是用来干嘛的呢，你可以在上面二分出要买几升果汁最少花多少钱。
时间复杂度 $O(n\log^2n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1<<17;
int n,m,p[N+10],res[N+10];
ll mon[N+10],wat[N+10],lit[N+10],pay[N+10],all;
bool ok[N+10];
vector<pair<int,int> >v[N+10];
void ADD(int pri,int amt){all+=amt;for(int i=pri;i<=N;i+=i&-i)lit[i]+=amt,pay[i]+=1ll*pri*amt;}//price,amount
ll ASK(ll amt){
int i=N;ll cst=0;
// printf("%lld:\n",amt);
for(int j=17;j>=0;j--){
if(i<(1<<j))continue;
// printf("%d:%d %d:%d,%d %d\n",i,j,i-(1<<j),lit[i-(1<<j)],pay[i-(1<<j)],amt);
if(lit[i-(1<<j)]>=amt)i-=(1<<j);else amt-=lit[i-(1<<j)],cst+=pay[i-(1<<j)];
}
cst+=i*amt;
// printf("%lld,%d,%lld\n",amt,i,cst);
return cst;
}
void solve(int l,int r,int L,int R){
if(l==r){
// printf("[%d]:",l);for(int i=L;i<=R;i++)printf("%d ",p[i]);puts("");
for(int i=L;i<=R;i++)res[p[i]]=l;
for(auto i:v[l])ADD(i.first,i.second);
return;
}
int mid=(l+r+1)>>1;
for(int i=mid;i<=r;i++)for(auto j:v[i])ADD(j.first,j.second);
// printf("%lld:[%d|%d|%d]:",all,l,mid,r);for(int i=L;i<=R;i++)printf("%d ",p[i]);puts("");
for(int i=L;i<=R;i++)ok[p[i]]=(all>=wat[p[i]]&&ASK(wat[p[i]])<=mon[p[i]]);
for(int i=mid;i<=r;i++)for(auto j:v[i])ADD(j.first,-j.second);
sort(p+L,p+R+1,[](int x,int y){return ok[x]>ok[y];});
int MID=L-1;while(MID<R&&ok[p[MID+1]])MID++;
solve(mid,r,L,MID),solve(l,mid-1,MID+1,R);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,x,y,z;i<=n;i++)scanf("%d%d%d",&x,&y,&z),v[x].push_back(make_pair(y,z));
for(int i=1;i<=m;i++)scanf("%lld%lld",&mon[i],&wat[i]),p[i]=i;
solve(0,N,1,m);
for(int i=1;i<=m;i++)printf("%d\n",!res[i]?-1:res[i]);
return 0;
}
```
# VI.可并堆（左偏树）
## VI.I.[【模板】左偏树（可并堆）](https://www.luogu.com.cn/problem/P3377)
什么？要你写一种数据结构，支持合并与删除 `min`？直接 `fhq treap` 它不香吗？
但是如果毒瘤出题人放到 $n=10^6$ 呢？平衡树卡的过去吗？
于是，一个明智的想法——左偏树便产生了。
具体而言，左偏树=堆+并查集，其中用并查集来维护合并集合的操作。
不过需要注意的是，这里的堆并不能用普通的堆，应该强制令堆**左偏**。具体而言，在堆中每个节点处，我们记录其**长儿子**，当发现右儿子是长儿子时，就交换两儿子，这样始终保证左儿子是长儿子。
这样子，在合并两个堆时——显然此时无论往左右哪个儿子去都是OK的——我们便强制往右儿子去。依照长链剖分的结论，这最多只会经过 $\log n$ 层。然后 `merge` 完后再手动 `pushup` 维护左偏即可。
这时候我们便看出为何要用并查集了——我们无法快速知道一个点所属堆的根（因为左偏树不是平衡的，假如这个儿子比较靠左其深度可能就是 $O(n)$ 级别的了，不能暴力跳父亲）。于是使用路径压缩并查集即可。
插入时直接合并，删除时合并左右儿子。需要注意的是，此时被删除的这个点**不能废物利用**，因其在并查集中可能在某些位置被存储为中间节点了。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool era[100100];
struct Heap{
int ch[2],dis,rt,val;
}q[100100];
#define lson q[x].ch[0]
#define rson q[x].ch[1]
void pushup(int x){
if(q[lson].dis<q[rson].dis)swap(lson,rson);
q[x].dis=q[rson].dis+1;
}
int findroot(int x){return q[x].rt==x?x:q[x].rt=findroot(q[x].rt);}
int merge(int x,int y){
if(!x||!y)return x+y;
if(x>y)swap(x,y);
if(q[x].val<=q[y].val){q[x].ch[1]=merge(q[x].ch[1],y),pushup(x);return x;}
else{q[y].ch[1]=merge(x,q[y].ch[1]),pushup(y);return y;}
}
void Merge(int x,int y){
if(era[x]||era[y])return;
x=findroot(x),y=findroot(y);
// printf("[%d,%d]\n",x,y);
if(x!=y)y=x^y^(x=merge(x,y)),q[y].rt=x;
}
int Pop(int x){
if(era[x]==true)return -1;
x=findroot(x),era[x]=true;
int u=lson,v=rson;
v=(u=merge(u,v))^u^v,q[u].rt=q[v].rt=q[x].rt=u;
return q[x].val;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&q[i].val),q[i].dis=1,q[i].rt=i;
for(int i=1,tp,x,y;i<=m;i++){
scanf("%d%d",&tp,&x);
if(tp==1)scanf("%d",&y),Merge(x,y);
else printf("%d\n",Pop(x));
// for(int x=1;x<=n;x++)printf("(%d,%d,%d)",lson,rson,q[x].rt);puts("");
}
return 0;
}
```
## VI.II.[[JLOI2015]城池攻占](https://www.luogu.com.cn/problem/P3261)
考虑在每个节点处维护该节点处还活着的骑士集合。显然该集合可以直接由子节点的集合们合并得出。
考虑删去那些在该节点处挂掉的骑士。发现其定是集合中最小的一些骑士。
因为每个骑士仅会被删去一次，所以暴力删去复杂度正确。
考虑集合中骑士在经历该节点的操作后，因为乘法恒正，所以大小关系不变，所以可以直接在左偏树上打 `tag` 维护。
当然，线段树合并/`fhq treap`/启发式合并/`pbds`亦可，其中 `fhq treap` 因为支持区间翻转因此还可以处理乘法 `tag` 为负的情形。
这题的左偏树实现得好连并查集都不用写，因此实现起来非常愉悦，就不用奇奇怪怪的方法了。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,id[300100],dep[300100],tp[300100],fa[300100];
ll del[300100],lim[300100],res[300100],ser[300100];
#define lson q[x].ch[0]
#define rson q[x].ch[1]
struct Heap{
int ch[2],dis;
ll tagadd,tagmul,val;
}q[300100];
void ADD(int x,ll y){q[x].tagadd+=y,q[x].val+=y;}
void MUL(int x,ll y){q[x].tagmul*=y,q[x].tagadd*=y,q[x].val*=y;}
void pushdown(int x){if(lson)MUL(lson,q[x].tagmul),ADD(lson,q[x].tagadd);if(rson)MUL(rson,q[x].tagmul),ADD(rson,q[x].tagadd);q[x].tagmul=1,q[x].tagadd=0;}
void pushup(int x){if(q[lson].dis<q[rson].dis)swap(lson,rson);q[x].dis=q[rson].dis+1;}
int merge(int x,int y){
if(!x||!y)return x+y;
if(q[x].val<=q[y].val){pushdown(x),q[x].ch[1]=merge(q[x].ch[1],y),pushup(x);return x;}
else{pushdown(y),q[y].ch[1]=merge(x,q[y].ch[1]),pushup(y);return y;}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%lld",&lim[i]);
dep[1]=1;for(int i=2;i<=n;i++)scanf("%d%d%lld",&fa[i],&tp[i],&del[i]),dep[i]=dep[fa[i]]+1;
for(int i=1,x;i<=m;i++)scanf("%lld%d",&q[i].val,&x),res[i]=dep[x],id[x]=merge(id[x],i);
for(int i=n;i;i--){
while(id[i]&&q[id[i]].val<lim[i])res[id[i]]-=dep[i],ser[i]++,pushdown(id[i]),id[i]=merge(q[id[i]].ch[0],q[id[i]].ch[1]);
if(tp[i])MUL(id[i],del[i]);else ADD(id[i],del[i]);
if(i!=1)id[fa[i]]=merge(id[fa[i]],id[i]);
}
for(int i=1;i<=n;i++)printf("%d\n",ser[i]);
for(int i=1;i<=m;i++)printf("%d\n",res[i]);
return 0;
}
```
## VI.III.[[APIO2012]派遣](https://www.luogu.com.cn/problem/P1552)
可以用线段树合并，每次在线段树上二分出最长的和不大于 $m$ 的前缀，但是左偏树明显码量更小，因为我们只需要在每个节点处记录现行的忍者集合，父亲的集合可以直接由儿子的集合合并得到，然后每次删掉集合中最贵的忍者直到整个集合中所有忍者的价格之和不大于 $m$，即可。
时间复杂度 $O(n\log n)$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,rt[100100],fa[100100],led[100100],sz[100100];
ll sum[100100],res;
#define lson q[x].ch[0]
#define rson q[x].ch[1]
struct Heap{int ch[2],dis,val;}q[100100];
void pushup(int x){if(q[lson].dis<q[rson].dis)swap(lson,rson);q[x].dis=q[rson].dis+1;}
int merge(int x,int y){
if(!x||!y)return x+y;
if(q[x].val>q[y].val){q[x].ch[1]=merge(q[x].ch[1],y),pushup(x);return x;}
else{q[y].ch[1]=merge(x,q[y].ch[1]),pushup(y);return y;}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d%d",&fa[i],&q[i].val,&led[i]),q[i].dis=1,rt[i]=i,sum[i]=q[i].val,sz[i]=1;
for(int i=n;i;i--){
while(sum[i]>m)sum[i]-=q[rt[i]].val,sz[i]--,rt[i]=merge(q[rt[i]].ch[0],q[rt[i]].ch[1]);
res=max(res,1ll*led[i]*sz[i]);
rt[fa[i]]=merge(rt[fa[i]],rt[i]),sum[fa[i]]+=sum[i],sz[fa[i]]+=sz[i];
}
printf("%lld\n",res);
return 0;
}
```