本篇包含树上主席树、可持久化并查集、CDQ 分治套 CDQ 分治、CDQ 分治优化 DP 等内容，例题都是知识点的进阶，请在知识点基础上学习。
第一篇
第二篇
该系列已加入洛谷保存站大套餐。

第三部分（续）

2.树上主席树模板
P2633 Count on a tree
不用看题，树上链第 $k$ 小。
这道题乍一看又像是树链剖分又像是主席树。
实际上是一道极好的主席树例题，可以先想5分钟正解。

---

欢迎回来。
其实很简单。看到是离线就知道不能树上整体二分，考虑主席树。注意到主席树是一种“可加”的数据结构，可以通过差分和前缀和计算区间，对于树上链条要怎么计算前缀和？将新版本的权值线段树建立在父亲节点的树上即可，计算时使用树上差分，将 $u$ 版本的节点值加 $v$ 版本的节点值再减去 $LCA(u,v)$ 版本的节点值和 $fa_{LCA(u,v)}$ 版本的节点值即可得到链上的权值线段树某个节点的节点值。其它的按照标准的主席树差分求第 $k$ 小值编码即可。还是能用到树链剖分，不过是用来求 LCA 的（LCA 肯定是树剖最快啊，怎么会有人用树上倍增呢）。代码中在 dfs1 中建主席树的版本。
$Code:$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
int lstans,n,m,M,fa[N],son[N],sz[N],head[N],dep[N],top[N],tot,cnt,a[N],b[N],root[N];
struct tree{
    int l,r,v;
}t[N<<5];
struct node{
    int v,nxt;
}tu[N<<1];
void add(int u,int v){tu[++tot]={v,head[u]},head[u]=tot;tu[++tot]={u,head[v]},head[v]=tot;}
void update(int &p,int pre,int l,int r,int x){
    t[++cnt]=t[pre];
    t[cnt].v++;
    p=cnt;
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid)update(t[p].l,t[pre].l,l,mid,x);
    else update(t[p].r,t[pre].r,mid+1,r,x);
}
int query(int x,int y,int lca,int lcafa,int l,int r,int k){
    if(l==r)return l;
    int p=t[t[x].l].v+t[t[y].l].v-t[t[lca].l].v-t[t[lcafa].l].v;
    int mid=l+r>>1;
    if(p>=k)return query(t[x].l,t[y].l,t[lca].l,t[lcafa].l,l,mid,k);
    return query(t[x].r,t[y].r,t[lca].r,t[lcafa].r,mid+1,r,k-p);
}
void dfs1(int u,int lst){
    dep[u]=dep[lst]+1;
    fa[u]=lst;
    update(root[u],root[fa[u]],1,M,a[u]);
    sz[u]=1;
    for(int i=head[u];i;i=tu[i].nxt){
        if(tu[i].v==lst)continue;
        dfs1(tu[i].v,u);
        sz[u]+=sz[tu[i].v];
        if(sz[tu[i].v]>sz[son[u]])son[u]=tu[i].v;
    }
}
void dfs2(int u,int topx){
    top[u]=topx;
    if(!son[u])return;
    dfs2(son[u],topx);
    for(int i=head[u];i;i=tu[i].nxt)
        if(tu[i].v!=fa[u]&&tu[i].v!=son[u])
            dfs2(tu[i].v,tu[i].v);
}
int LCA(int x,int y){
    while(top[x]!=top[y])dep[top[x]]>=dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
	n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=b[i]=read();
    sort(b+1,b+n+1);
    M=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+M+1,a[i])-b;
    for(int i=1;i<n;++i)add(read(),read());
    dfs1(1,0),dfs2(1,1);
    while(m--){
        int x=read()^lstans,y=read(),z=LCA(x,y);
        lstans=b[query(root[x],root[y],root[z],root[fa[z]],1,M,read())];
        write(lstans),putchar('\n');
    }
	return 0;
}

时间复杂度： $O((M+N)logN))$
3.P2468 [SDOI2010] 粟粟的书架
还是有一定难度的。
这次没写最优解主席树，而是写了整体二分（没忍住）。
标准做法是当作二合一题做，后半是主席树二分的模板，索引为从大到小排序的书本厚度，二分需要拿的最薄的书籍，如果左节点足够厚就递归左节点，否则递归右节点。前半部分大部分题解用了毫无美感（暴论）的二维前缀和+二分，枚举权值 $p$，维护 $(1,1)$ 到 $(i,j)$ 的矩阵大于等于 $k$ 的数的总和以及这个矩阵中大于等于 $k$ 的数的个数并二分，利用 $0\leq p_{i,j}\leq 1000$ 的特殊性质用 $O(RCmax\{p_{i,j}\})$ 的时间复杂度卡过第一问，也有一些神犇优美地用二维差分主席树解掉达到所有点 $O(RClog_2(RC))$的时间复杂度，值得学习👍。
但是我们不用主席树。注意到这题和国家集训队的矩阵乘法那题很像，可以从厚到薄排序然后用整体二分解决。只需要在整体二分中累加答案即可，分到右组时加上需要添加的书籍数量，甚至不用写两份代码，准备两个大小不同的树状数组即可。注意整体二分的二分与一般二分不同，找第一个不符合的值域（或下标）时要特判，如图：

时间复杂度每个点都是 $O(RClog^2(RC))$.
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)|48);
}
struct num{
    int x,y,v;
    bool operator < (const num&b)const{return v>b.v;}
}a[500005];
struct order{
    int ax,ay,bx,by,k,id,ans;
    bool operator < (const order&b)const{return id<b.id;}
}q[200005],q1[200005],q2[200005];
int r,c,n,m,tree1[205][205][2],tree2[2][500005][2],x,y,k,maxn,use;
void add(int x,int y,int k,int k2){
    for(int i=x;i<=r;i+=i&(-i))
        for(int j=y;j<=c;j+=j&(-j))
            use?tree1[i][j][0]+=k:tree2[i][j][0]+=k,use?tree1[i][j][1]+=k2:tree2[i][j][1]+=k2;
}
int sum(int x,int y,bool one){
    int ans=0;
    for(int i=x;i;i-=i&(-i))
        for(int j=y;j;j-=j&(-j))
            ans+=use?tree1[i][j][one]:tree2[i][j][one];
    return ans;
}
bool inside(order x,num y){return x.ax<=y.x&&y.x<=x.bx&&x.ay<=y.y&&y.y<=x.by;}
int msum(int ax,int ay,int bx,int by,bool one){return sum(bx,by,one)-sum(ax-1,by,one)-sum(bx,ay-1,one)+sum(ax-1,ay-1,one);}
void solve(int l,int r,int ql,int qr){
    if(ql>qr)return;
    int cnt1=0,cnt2=0,mid=l+r>>1;
    if(l==r){
        for(int i=ql;i<=qr;++i)if(q[i].k>0&&inside(q[i],a[l]))q[i].k-=a[l].v,q[i].ans++;
        return;
    }
    bool b1=0,b2=0;
    for(int i=l;i<=mid;++i)add(a[i].x,a[i].y,a[i].v,1);
    for(int i=ql;i<=qr;++i){
        int t=msum(q[i].ax,q[i].ay,q[i].bx,q[i].by,0);
        if(q[i].k<t)q1[++cnt1]=q[i],b1=1;
        else q[i].k-=t,q2[++cnt2]=q[i],b2=1,q2[cnt2].ans+=msum(q[i].ax,q[i].ay,q[i].bx,q[i].by,1);
    }
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    for(int i=l;i<=mid;++i)add(a[i].x,a[i].y,-a[i].v,-1);
    if(b1)solve(l,mid,ql,ql+cnt1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr);
}
signed main(){
    r=read(),c=read(),m=read(),use=(r!=1);
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j)
            a[++n]={i,j,read()},maxn=max(maxn,a[n].v);
    sort(a+1,a+n+1);
    for(int i=1;i<=m;++i)q[i]={read(),read(),read(),read(),read(),i};
    solve(1,n,1,m);
    sort(q+1,q+m+1);
    for(int i=1;i<=m;++i){
        if(q[i].k<=0)write(q[i].ans),putchar('\n');
        else printf("Poor QLW\n");
    }
    return 0;
}

4.水题：P7424 [THUPC 2017] 天天爱射击
肥肠简单，请先自行构思。

---

如果把每个子弹当作询问的话，处理射击后的每个木板的状况会很麻烦。考虑整体二分，综上所述只能把木板当作询问，直接二分第几发子弹射出后木板破碎，这就在树状数组的解决范围内了，统计对每个木板来说 $mid$ 发子弹发出后有多少打在这个木板区间内即可 check.最后确定答案时，把贡献算在最后这发打坏木板的子弹上就行了。小 Trick: 整体二分时将值域加一，这样完成不了的询问就会落在值域加一的答案区间，这题中可以将这些答案忽略掉因为加到第 $m+1$ 个子弹的答案不算数（只有 $m$ 发）不会输出。
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)|48);
}
struct xyl{
    int l,r,k;
}q[200005],q1[200005],q2[200005];
int n,m,a[200005],ans[200005],tree[200005];
void add(int x,int k){for(int i=x;i<=200000;i+=i&(-i))tree[i]+=k;}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=i&(-i))res+=tree[i];
    return res;
}
void solve(int l,int r,int ql,int qr){
    if(ql>qr)return;
    if(l==r){ans[l]+=qr-ql+1;return;}
    int cnt1=0,cnt2=0,mid=l+r>>1;
    bool b1=0,b2=0;
    for(int i=l;i<=mid;++i)add(a[i],1);
    for(int i=ql;i<=qr;++i){
        int t=sum(q[i].r)-sum(q[i].l-1);
        if(q[i].k<=t)q1[++cnt1]=q[i],b1=1;
        else q[i].k-=t,q2[++cnt2]=q[i],b2=1;
    }
    for(int i=l;i<=mid;++i)add(a[i],-1);
    for(int i=1;i<=cnt1;++i)q[ql+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i)q[ql+cnt1+i-1]=q2[i];
    if(b1)solve(l,mid,ql,ql+cnt1-1);
    if(b2)solve(mid+1,r,ql+cnt1,qr);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)q[i]={read(),read(),read()};
    for(int i=1;i<=m+1;++i)a[i]=i==m+1?1:read();
    solve(1,m+1,1,n);
    for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
    return 0;
}

时间复杂度： $O((N+M)log^2M)$
5.
一道毒瘤来啦！
P9175 [COCI 2022/2023 #4] Mreža
依旧 COCI.
自行看题。
有不同做法，这里采用时间复杂度最优的算法。可以使用 P2633 的树上主席树技巧，转化为树上主席树二分。首先将 $v_i$ 和 $s_i$ 共同离散化（就是因为一不小心离散化了两个后面才没 WA,纯运来的，实际上这一步不是必要的）以 $v_i$ 为下标建立权值线段树，叶子节点值为 $c_i$,维护每个 $v_i$ 区间的 $c_i$ 总和，如果预算够就往右递归，否则往左递归。除此以外，单独计算链上 $s_i$ 最小值，取这两个答案的最小值即可。
可以用树上 ST 表求解链上最小值，设 $fa_{i,u}$ 为节点 $u$ 向上 $2^i$ 个祖先，$st_{i,u}$ 为从节点 $u$ 向根节点延伸的长度为 $2^i$ 的链上的最小值，有：

$$st_{i,u}=min(st_{i-1,u},st_{i-1,fa_{i-1,u}})$$

区间的合并如图所示：

然后像倍增 LCA 一样先让低的跳，如果一个是另一个的祖先就返回，否则一起跳，跳到 LCA 的下一层，最后再跳 LCA 这层即可。
时间复杂度：$O((n+q)log_2n)$
目前无特意卡常跑进除隐私保护外第6优解，但是离散化了还没跑过卡常+没离散化的某篇题解，之所以题解可以不用离散化是因为主席树动态加点只会给 update 过的节点开空间，其它空间不会浪费，因此空间开到 $O(nlog_2V)$ 即可。
$Code:$

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int n,m,head[N],dep[N],tot,cnt,root[N],fa[17][N],st[17][N],from[N],tmp[N],idx,X,Y,C;
struct tree{
    int l,r,v;
}t[N<<6];
struct node{
    int v,nxt,o,c,s;
}tu[N<<1];
void add(int s,int c,int o,int v,int u){X=o,Y=s,tu[++tot]={v,head[u],o,c,s},head[u]=tot;tu[++tot]={u,head[v],o,c,s},head[v]=tot;}
void update(int &p,int pre,int l,int r,int x,int k){
    t[++cnt]=t[pre];
    t[cnt].v+=k;
    p=cnt;
    if(l==r)return;
    int mid=l+r>>1;
    if(x<=mid)update(t[p].l,t[pre].l,l,mid,x,k);
    else update(t[p].r,t[pre].r,mid+1,r,x,k);
}
int query(int x,int y,int lca,int l,int r,int k){
    if(l==r)return l;
    int p=t[t[x].l].v+t[t[y].l].v-2*t[t[lca].l].v;
    int mid=l+r>>1;
    if(p>k)return query(t[x].l,t[y].l,t[lca].l,l,mid,k);
    return query(t[x].r,t[y].r,t[lca].r,mid+1,r,k-p);
}
void dfs(int u,int lst){
    dep[u]=dep[lst]+1;
    if(u^1)update(root[u],root[lst],1,idx,tu[from[u]].o,tu[from[u]].c);
    fa[0][u]=lst;
    st[0][u]=tu[from[u]].s;
    for(int i=1;i<17;++i)fa[i][u]=fa[i-1][fa[i-1][u]],st[i][u]=min(st[i-1][u],st[i-1][fa[i-1][u]]);
    for(int i=head[u];i;i=tu[i].nxt){
        if(tu[i].v==lst)continue;
        from[tu[i].v]=i;
        dfs(tu[i].v,u);
    }
}
pair<int,int> LCA(int x,int y){
    int res=1e9;
    if(dep[x]<dep[y])swap(x,y);
    if(dep[x]>dep[y])
        for(int i=16;i>=0;--i)
            if(dep[fa[i][x]]>=dep[y])
                res=min(res,st[i][x]),x=fa[i][x];
    if(x==y)return {x,res};
    for(int i=16;i>=0;--i)
        if(fa[i][x]!=fa[i][y])
            res=min(res,min(st[i][x],st[i][y])),x=fa[i][x],y=fa[i][y];
    return {fa[0][x],min(res,min(st[0][x],st[0][y]))};
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
	n=read();
    for(int i=0;i<17;++i)st[i][0]=1e9;
    for(int i=1;i<n;++i)add(read(),read(),read(),read(),read()),tmp[++idx]=X,tmp[++idx]=Y;
    sort(tmp+1,tmp+idx+1);
    idx=unique(tmp+1,tmp+idx+1)-tmp-1;
    for(int i=1;i<=tot;++i)tu[i].o=lower_bound(tmp+1,tmp+idx+1,tu[i].o)-tmp,tu[i].s=lower_bound(tmp+1,tmp+idx+1,tu[i].s)-tmp;
    dfs(1,0);
    m=read();
    while(m--){
        X=read(),Y=read(),C=read();
        pair<int,int> pii=LCA(X,Y);
        write(tmp[min(pii.second,query(root[X],root[Y],root[pii.first],1,idx,C))]),putchar('\n');
    }
	return 0;
}

6.P3402 【模板】可持久化并查集
这题很罕见地考模板不强制在线，导致题解区有很多离线的 $O(Nlog_2N)$ 做法，如果想练习可持久化并查集请自觉 （不是）。
首先，可持久化数据结构不可以用任何均摊，所以合并不能使用路径压缩，可以用时间复杂度稳定为单次 $O(log_2N)$ 的按秩合并进行合并。按秩合并采用高度法，将高度小的数作为高度大的树根的儿子。用主席树维护 fa 数组和 dep 数组的更改。注意这里一次修改要开两条链，一条连向 fa 更新的叶子节点一条连向 dep 更新的叶子节点，因为按秩合并时 fa 头儿子 dep 头爸爸。每次修改都进行一次主席树操作，时空复杂度 $O(Nlog^2N)$.
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)|48);
}
const int N=300005;
int n,m,cnt,root[N],op,x;
struct node{
    int l,r,fa,dep;
}t[N<<5];
void build(int &cur,int l,int r){
    cur=++cnt;
    if(l==r){
        t[cnt].fa=l;
        return;
    }
    int mid=l+r>>1;
    build(t[cur].l,l,mid),build(t[cur].r,mid+1,r);
}
int pos(int cur,int l,int r,int x){
    if(l==r)return cur;
    if((l+r>>1)>=x)return pos(t[cur].l,l,l+r>>1,x);
    return pos(t[cur].r,(l+r>>1)+1,r,x);
}
int find(int cur,int x){
    int fa=pos(root[cur],1,n,x);
    if(t[fa].fa==x)return fa;
    return find(cur,t[fa].fa);
}
void getfa(int &cur,int pre,int l,int r,int x,int y){
    cur=++cnt;
    t[cnt]=t[pre];
    if(l==r){
        t[cnt].fa=y;
        return;
    }
    int mid=l+r>>1;
    if(mid>=x)getfa(t[cur].l,t[pre].l,l,mid,x,y);
    else getfa(t[cur].r,t[pre].r,mid+1,r,x,y);
}
void deepen(int &cur,int pre,int l,int r,int x){
    cur=++cnt;
    t[cur]=t[pre];
    if(l==r){
        t[cur].dep++;
        return;
    }
    int mid=l+r>>1;
    if(mid>=x)deepen(t[cur].l,t[pre].l,l,mid,x);
    else deepen(t[cur].r,t[pre].r,mid+1,r,x);
}
void merge(int cur,int x,int y){
    root[cur]=root[cur-1];
    x=find(cur,x),y=find(cur,y);
    if(t[x].fa!=t[y].fa){
        if(t[x].dep>t[y].dep)swap(x,y);
        getfa(root[cur],root[cur-1],1,n,t[x].fa,t[y].fa);
        if(t[x].dep==t[y].dep)deepen(root[cur],root[cur],1,n,t[y].fa);
    }
}
bool check(int cur,int x,int y){
    x=find(cur,x),y=find(cur,y);
    return t[x].fa==t[y].fa;
}
signed main(){
    n=read(),m=read();
    build(root[0],1,n);
    for(int i=1;i<=m;++i){
        op=read(),x=read();
        if(op==1)merge(i,x,read());
        if(op==2)root[i]=root[x];
        if(op==3){
            write(check(i-1,x,read())),putchar('\n');
            root[i]=root[i-1];
        }
    }
    return 0;
}

各种函数意义看英文字面意思。pos 函数是辅助按秩合并的，它返回某个版本第 k 个元素在动态开点的主席树内的编号。

CDQ 分治进阶

7.P3769 [CH弱省胡策R2] TATT
直到做完这道题都不知道题目是什么意思
四维空间最长上升子序列。需要 CDQ 分治套 CDQ 分治和 CDQ 优化 DP 的技巧。
这里先说 CDQ 的顺序。对于 cdq2 函数，定义 cdq2(l,r) 意为计算 $[l,mid]$ 区间对 $[mid+1,r]$ 区间元素的贡献。按照 DP 从左到右的顺序，先分治左半部分的区间，计算好左半部分的答案，再计算左半部分对右半部分的贡献，最后分治右半区间计算右半部分内部互相的贡献。DP 计算用树状数组即可。
但是这是四维空间，要怎么用 CDQ 分治呢？可以用 CDQ 套 CDQ，一个 CDQ 解决第二维，嵌套另一个 CDQ 解决第三维。先回顾三维 CDQ:排序解掉第一维，左右子区间内部排序确保有序性然后双指针解决第二维，数据结构解决第三维。四维时如何确保第一维的有序性？注意到永远是第一维小的向第一维大的元素贡献答案， 可以在第一个 CDQ 中先计算左区间，然后（此时左边的第一维比右边的小）把左边的所有元素打上标记0，右边的打上1，再排序第二维，进入 cdq2,cdq2 中先计算左组，再将左右分别按第三维排序，双指针遍历，左区间该元素的标记为0则插入树状数组，右区间该元素的标记为1则计算答案，（所有被打上0的元素第一维都比所有打上1的小）完事清理树状数组并将右区间按第二维排序递归计算右区间。 于是能过矣。
注意到当双指针过后，DP 的值受到改变，树状数组清除时不知道该减去多少，不过插入树状数组的位置（第四维度的值）还存着，对于每个位置，树状数组把这个位置的数直接设为0即可。由于每次是计算区间 $[1,x]$ 的 DP 最大值，树状数组是可以的。
时间复杂度：$O(Nlog^3N)$
记得依旧查重。
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct xyl{
    int a,b,c,d,sz,id,op;
    bool operator!=(const xyl&x)const{return (x.a!=a||x.b!=b)||(x.c!=c||x.d!=d);}
}a[50005],k[50005];
int n,N,tree[50005],tmp[50005],idx,dp[50005],ans;
bool cmp1(xyl x,xyl y){return x.a!=y.a?x.a<y.a:x.b!=y.b?x.b<y.b:x.c!=y.c?x.c<y.c:x.d<y.d;}
bool cmp2(xyl x,xyl y){return x.b!=y.b?x.b<y.b:x.a!=y.a?x.a<y.a:x.c!=y.c?x.c<y.c:x.d<y.d;}
bool cmp3(xyl x,xyl y){return x.c<y.c;}
void add(int x,int d){for(int i=x;i<=idx;i+=i&-i)tree[i]=max(tree[i],d);}
int maxn(int x){int sum=0;for(int i=x;i;i-=i&-i)sum=max(sum,tree[i]);return sum;}
void clr(int x){for(int i=x;i<=idx;i+=i&-i)tree[i]=0;}
void cdq2(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq2(l,mid);
    sort(a+l,a+mid+1,cmp3),sort(a+mid+1,a+r+1,cmp3);
    for(;cnt2<=r;++cnt2){
        for(;cnt1<=mid&&a[cnt1].c<=a[cnt2].c;++cnt1)if(!a[cnt1].op)add(a[cnt1].d,dp[a[cnt1].id]);
        if(a[cnt2].op)dp[a[cnt2].id]=max(dp[a[cnt2].id],maxn(a[cnt2].d)+a[cnt2].sz);
    }
    for(int i=l;i<=mid;++i)if(!a[i].op)clr(a[i].d);
    sort(a+mid+1,a+r+1,cmp2);
    cdq2(mid+1,r);
}
void cdq1(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    cdq1(l,mid);
    for(int i=l;i<=r;++i)a[i].op=i>mid;
    sort(a+l,a+r+1,cmp2);
    cdq2(l,r);
    sort(a+l,a+r+1,cmp1);
    cdq1(mid+1,r);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)k[i]={read(),read(),read(),read(),0,i,0},tmp[++idx]=k[i].d;
    sort(tmp+1,tmp+idx+1);
    idx=unique(tmp+1,tmp+idx+1)-tmp-1;
    for(int i=1;i<=n;++i)k[i].d=lower_bound(tmp+1,tmp+idx+1,k[i].d)-tmp;
    sort(k+1,k+n+1,cmp1);
    for(int i=1;i<=n;++i){
        if(k[i]!=k[i-1])a[++N]=k[i],a[N].id=N;
        a[N].sz++,dp[N]=a[N].sz;
    }
    cdq1(1,N);
    for(int i=1;i<=N;++i)ans=max(ans,dp[i]);
    write(ans);
    return 0;
}

8.P4849 寻找宝藏
比较难的题。 CDQ 套 CDQ 的部分不讲了（这里给出的 CDQ 代码略有不同，不过意思是一样的，自己想），我们来讲讲 DP.
下文的长度表示最长上升子序列长度。计算 $i$ 结尾的方案数，我们遍历 $j$ 符合条件的 $dp_j$ 值，如果 $i$ 目前的最长子序列长度小于 $j$ 计算的长度值，将 $i$ 的最长子序列长度和方案数设为当前 $j$ 的值（很好理解），如果恰好相等，说明又有一种方法达到当前的 $dp_i$ 值，将方案数加上当前遍历元素的方案数（也很好理解）。树状数组计算时也按这个思路统计答案，最后直接返回计算到的答案，修改时如果当前位置的长度小于插入值的长度就设其为插入值的长度，相等则累加方案数。为什么正确？DP 式中需要的是长度的最大值，由于树状数组每个元素存储的是一个区间内的元素信息，可以把不同区间的答案合并。
时间复杂度： $O(Nlog^3N)$
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct xyl{
    int a,b,c,d,sz,id,op;
    bool operator!=(const xyl&x)const{return (x.a!=a||x.b!=b)||(x.c!=c||x.d!=d);}
}k[80005],a[80005];
int n,N,m,t[80005],t2[80005],tmp[80005],idx,dp[80005],ans,sum,dq[80005],mod=998244353;
bool cmp1(xyl x,xyl y){return x.a!=y.a?x.a<y.a:x.b!=y.b?x.b<y.b:x.c!=y.c?x.c<y.c:x.d<y.d;}
bool cmp2(xyl x,xyl y){return x.b!=y.b?x.b<y.b:x.a!=y.a?x.a<y.a:x.c!=y.c?x.c<y.c:x.d<y.d;}
bool cmp3(xyl x,xyl y){return x.c!=y.c?x.c<y.c:x.a!=y.a?x.a<y.a:x.b!=y.b?x.b<y.b:x.d<y.d;}
void add(int x,int d,int y){
    for(;x<=idx;x+=x&-x){
        if(d>t[x])t[x]=d,t2[x]=y;
        else if(d==t[x])(t2[x]+=y)%=mod;
    }
}
void qry(int x,int &f,int &sum,int v){
    for(;x;x-=x&-x){
        if(t[x]+v>f)f=t[x]+v,sum=t2[x];
        else if(t[x]+v==f)(sum+=t2[x])%=mod;
    }
}
void clr(int x){for(;x<=idx;x+=x&-x)t[x]=t2[x]=0;}
void cdq2(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq2(l,mid);
    sort(k+l,k+mid+1,cmp3),sort(k+mid+1,k+r+1,cmp3);
    for(;cnt2<=r;++cnt2){
        for(;cnt1<=mid&&k[cnt1].c<=k[cnt2].c;++cnt1)if(!k[cnt1].op)add(k[cnt1].d,dp[k[cnt1].id],dq[k[cnt1].id]);
        if(k[cnt2].op)qry(k[cnt2].d,dp[k[cnt2].id],dq[k[cnt2].id],k[cnt2].sz);
    }
    for(int i=l;i<=mid;++i)if(!k[i].op)clr(k[i].d);
    sort(k+l,k+r+1,cmp2);
    cdq2(mid+1,r);
}
void cdq1(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    cdq1(l,mid);
    for(int i=l;i<=r;++i)k[i]=a[i],k[i].op=i>mid;
    sort(k+l,k+r+1,cmp2);
    cdq2(l,r);
    cdq1(mid+1,r);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i)k[i]={read(),read(),read(),read(),read(),0,0},tmp[++idx]=k[i].d;
    sort(tmp+1,tmp+idx+1);
    idx=unique(tmp+1,tmp+idx+1)-tmp-1;
    for(int i=1;i<=n;++i)k[i].d=lower_bound(tmp+1,tmp+idx+1,k[i].d)-tmp;
    sort(k+1,k+n+1,cmp1);
    for(int i=1;i<=n;++i){
        if(k[i]!=k[i-1])a[++N]=k[i],a[N].id=N;
        else a[N].sz+=k[i].sz;
    }
    for(int i=1;i<=N;++i)dp[i]=a[i].sz,dq[i]=1;
    cdq1(1,N);
    for(int i=1;i<=N;++i){
        if(dp[i]>ans)
            ans=dp[i],sum=dq[i];
        else if(dp[i]==ans)
            sum+=dq[i],sum%=mod;
    }
    write(ans),putchar('\n'),write(sum);
    return 0;
}

9.P5621 [DBOI2019] 德丽莎世界第一可爱
毒瘤，和上题差不多，只不过值域有负数和零。查重和树状数组的部分有不同，答案初始是 -INF，并取 sz 的最大值；去重合并同类项时如果贡献是负数就不累加；树状数组初始化和删除是 -INF.时间复杂度懒得打了一模一样。

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct xyl{
    int a,b,c,d,sz,id,op;
    bool operator!=(const xyl&x)const{return (x.a!=a||x.b!=b)||(x.c!=c||x.d!=d);}
}a[50005],k[50005];
int n,N,tree[50005],tmp[50005],idx,dp[50005],ans=-1e18;
bool cmp1(xyl x,xyl y){return x.a!=y.a?x.a<y.a:x.b!=y.b?x.b<y.b:x.c!=y.c?x.c<y.c:x.d!=y.d?x.d<y.d:x.sz>y.sz;}
bool cmp2(xyl x,xyl y){return x.b!=y.b?x.b<y.b:x.a!=y.a?x.a<y.a:x.c!=y.c?x.c<y.c:x.d!=y.d?x.d<y.d:x.sz>y.sz;}
bool cmp3(xyl x,xyl y){return x.c!=y.c?x.c<y.c:x.a!=y.a?x.a<y.a:x.b!=y.b?x.b<y.b:x.d!=y.d?x.d<y.d:x.sz>y.sz;}
void add(int x,int d){for(int i=x;i<=idx;i+=i&-i)tree[i]=max(tree[i],d);}
int maxn(int x){int sum=-1e18;for(int i=x;i;i-=i&-i)sum=max(sum,tree[i]);return sum;}
void clr(int x){for(int i=x;i<=idx;i+=i&-i)tree[i]=-1e18;}
void cdq2(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq2(l,mid);
    sort(a+l,a+mid+1,cmp3),sort(a+mid+1,a+r+1,cmp3);
    for(;cnt2<=r;++cnt2){
        for(;cnt1<=mid&&a[cnt1].c<=a[cnt2].c;++cnt1)if(!a[cnt1].op)add(a[cnt1].d,dp[a[cnt1].id]);
        if(a[cnt2].op)dp[a[cnt2].id]=max(dp[a[cnt2].id],maxn(a[cnt2].d)+a[cnt2].sz);
    }
    for(int i=l;i<=mid;++i)if(!a[i].op)clr(a[i].d);
    sort(a+mid+1,a+r+1,cmp2);
    cdq2(mid+1,r);
}
void cdq1(int l,int r){
    if(l==r)return;
    int mid=l+r>>1;
    cdq1(l,mid);
    for(int i=l;i<=r;++i)a[i].op=i>mid;
    sort(a+l,a+r+1,cmp2);
    cdq2(l,r);
    sort(a+l,a+r+1,cmp1);
    cdq1(mid+1,r);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)k[i]={read(),read(),read(),read(),read(),i,0},tmp[++idx]=k[i].d,ans=max(ans,k[i].sz);
    sort(tmp+1,tmp+idx+1);
    idx=unique(tmp+1,tmp+idx+1)-tmp-1;
    for(int i=1;i<=n;++i)k[i].d=lower_bound(tmp+1,tmp+idx+1,k[i].d)-tmp;
    sort(k+1,k+n+1,cmp1);
    for(int i=1;i<=n;++i){
        if(k[i]!=k[i-1])a[++N]=k[i],a[N].id=N;
        else a[N].sz+=max(0ll,k[i].sz);
        ans=max(ans,a[N].sz);
    }
    for(int i=1;i<=N;++i)dp[i]=a[i].sz;
    for(int i=0;i<=idx;++i)tree[i]=-1e18;
    cdq1(1,N);
    for(int i=1;i<=N;++i)ans=max(ans,dp[i]);
    write(ans);
    return 0;
}

10.P2487 [SDOI2011] 拦截导弹
前一问和寻找宝藏差不多，只不过是三维的。注意树状数组要统计更大值（看题！），所以树状数组的索引用 $m-a_{i_v}+1$.双指针的判断部分也是反的。
第二问：反着计算最长上升子序列长度和方案数。将 $id$ 和 $a_{i_v}$ 倒过来，$a_{i_h}$ 取相反数然后再跑一遍 CDQ 就行了。接下来可以把值域这样把两个答案并在一起（加在一起再减去重复计算的当前元素，也就是说-1），如果等于全局最长上升子序列长度就说明是方案的一部分，两个答案的方案数相乘即是贡献的方案数，最后除以全局最长上升子序列的方案数得到概率；否则输出0（不在最优方案中）。$O(Nlog^2N)$.
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct xyl{
    int id,h,v;
}a[50005];
struct dp{
    int f;double g;
}dp1[50005],dp2[50005],t[50005],dpk;
int n,m,tmp[50005],ans;double sum;
bool cmp1(xyl x,xyl y){return x.id<y.id;}
bool cmp2(xyl x,xyl y){return x.h>y.h;}
void add(int x,dp d){for(;x<=m;x+=x&-x)if(t[x].f<d.f)t[x]=d;else t[x].g+=(t[x].f==d.f)*d.g;}
dp qry(int x){
    dp res={0,0};
    for(;x;x-=x&-x)
        if(res.f<t[x].f)res=t[x];
        else if(res.f==t[x].f)res.g+=t[x].g;
    return res;
}
void del(int x){for(;x<=m;x+=x&-x)t[x]={0,0};}
void cdq(int l,int r){
    if(l==r)return;
    int mid=l+r>>1,cnt1=l,cnt2=mid+1;
    cdq(l,mid);
    sort(a+l,a+mid+1,cmp2),sort(a+mid+1,a+r+1,cmp2);
    for(;cnt2<=r;++cnt2){
        for(;cnt1<=mid&&a[cnt1].h>=a[cnt2].h;++cnt1)add(m-a[cnt1].v+1,dp1[a[cnt1].id]);
        dpk=qry(m-a[cnt2].v+1),++dpk.f;
        if(dp1[a[cnt2].id].f<dpk.f)dp1[a[cnt2].id]=dpk;
        else if(dp1[a[cnt2].id].f==dpk.f)dp1[a[cnt2].id].g+=dpk.g;
    }
    for(int i=l;i<=mid;++i)del(m-a[i].v+1);
    sort(a+l,a+r+1,cmp1);
    cdq(mid+1,r);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read();
    for(int i=1;i<=n;++i)a[i]={i,read(),read()},tmp[++m]=a[i].v,dp1[i]={1,1};
    sort(tmp+1,tmp+m+1),m=unique(tmp+1,tmp+m+1)-tmp-1;
    for(int i=1;i<=n;++i)a[i].v=lower_bound(tmp+1,tmp+m+1,a[i].v)-tmp;
    cdq(1,n);
    for(int i=1;i<=n;++i)ans=max(ans,dp1[i].f),dp2[i]=dp1[i];
    for(int i=1;i<=n;++i)if(ans==dp1[i].f)sum+=dp1[i].g;
    write(ans),putchar('\n');
    for(int i=1;i<=n;++i)dp1[i]={1,1},a[i]={n-a[i].id+1,-a[i].h,m-a[i].v+1};
    sort(a+1,a+n+1,cmp1);
    cdq(1,n);
    for(int i=1;i<=n;++i){
        if(dp1[n-i+1].f+dp2[i].f-1==ans)printf("%.5lf ",1.0*dp1[n-i+1].g*dp2[i].g/sum);
        else putchar('0'),putchar(' ');
    }
    return 0;
}

---

大抵不会再更新了。