DS进阶

DS

---

实际上最近并没有很大的学习DS的刚需，只是心态不好写点DS放松一下

可持久化线段树

说起来我写线段树的熟练度一直不够，还是太菜了

主席树板子

主席树

#include<bits/stdc++.h>
#define int long long
#define mid (l+r>>1)
using namespace std;
const int N=200005;
const int inf=1e9;
int a[N];
struct node{
    int ls,rs;
    int val;
}tr[N*33];
int idx;
int n,m;
void add(int &rt,int pre,int l,int r,int pos,int k){
    rt=++idx;
    tr[rt]=tr[pre];
    tr[rt].val+=k;
    if(l==r) return;
    if(pos<=mid) add(tr[rt].ls,tr[pre].ls,l,mid,pos,k);
    else add(tr[rt].rs,tr[pre].rs,mid+1,r,pos,k);
}
int query(int rt,int pre,int l,int r,int k){
    if(l==r) return l;
    int dta=tr[tr[rt].ls].val-tr[tr[pre].ls].val;
    if(dta>=k){
        return query(tr[rt].ls,tr[pre].ls,l,mid,k);
    }
    else return query(tr[rt].rs,tr[pre].rs,mid+1,r,k-dta);
}
int rot[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        add(rot[i],rot[i-1],0,inf,x,1);
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        cout<<query(rot[r],rot[l-1],0,inf,k)<<'\n';
    }
}

带修主席树

其实是树状数组套主席树。

P2617 Dynamic Rankings

看着跟板子可以说一模一样啊，但是这个修改承担不起，你没资格啊你没资格

套一个树状数组，变成 $\log n$ 个主席树跟 $\log n$ 个主席树相减，然后并不需要离散化也是可以过的，科技树加入了奇奇怪怪的东西

#include<bits/stdc++.h>
#define mid (l+r>>1)
using namespace std;
const int N=2e5+5;
const int inf=1e9;
struct node{
    int ls,rs;
    int v;
}tr[N*505];
int n,m;
int a[N];
int cnt[2];
int idx;
int rot[N];
int tmp[2][21];
void modi(int &rt,int l,int r,int pos,int k){
    if(!rt) rt=++idx;
    tr[rt].v+=k;
    if(l==r) return;
    if(pos<=mid) modi(tr[rt].ls,l,mid,pos,k);
    else modi(tr[rt].rs,mid+1,r,pos,k);
}
void add(int x,int val){
    for(int i=x;i<=n;i+=i&-i){
        modi(rot[i],0,inf,a[x],val);
    }
}
int query(int l,int r,int k){
    if(l==r) return l;
    int sum=0;
    for(int i=1;i<=cnt[1];i++) sum+=tr[tr[tmp[1][i]].ls].v;
    for(int i=1;i<=cnt[0];i++) sum-=tr[tr[tmp[0][i]].ls].v;
    if(k<=sum){
        for(int i=1;i<=cnt[1];i++) tmp[1][i]=tr[tmp[1][i]].ls;
        for(int i=1;i<=cnt[0];i++) tmp[0][i]=tr[tmp[0][i]].ls;  
        return query(l,mid,k);  
    }else{
        for(int i=1;i<=cnt[1];i++) tmp[1][i]=tr[tmp[1][i]].rs;
        for(int i=1;i<=cnt[0];i++) tmp[0][i]=tr[tmp[0][i]].rs;  
        return query(mid+1,r,k-sum);  
    }
}
int ask(int l,int r,int k){
    memset(tmp,0,sizeof tmp);
    cnt[0]=cnt[1]=0;
    for(int i=r;i>0;i-=i&-i) tmp[1][++cnt[1]]=rot[i]; 
    for(int i=l-1;i>0;i-=i&-i) tmp[0][++cnt[0]]=rot[i]; 
    return query(0,inf,k);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],add(i,1);
    for(int i=1,l,r,k;i<=m;i++){
        char opt;       
        cin>>opt;
        bool xixi=(opt=='Q');
        if (xixi){
            cin>>l>>r>>k;
            cout<<ask(l,r,k)<<"\n";
        }
        else{
            cin>>l>>k;
            add(l,-1);
            a[l]=k;
            add(l,1);
        }
    }
    return 0;
}

树上主席树

注意到大多数应用的时候是把主席树当做前缀树用，这里也不例外啊不例外

不带修改，直接类比树上差分即可，$s[u]+s[v]-s[lca]-s[fa[lca]]$ 就是答案，把这一坨用主席树代表即可

#include<bits/stdc++.h>
#define int long long
#define mid ((l+r)>>1)
using namespace std;
const int N=1e5+5;
const int inf=INT_MAX;
int n,a[N];
int m;
struct node{
    int ls,rs,val;
}tr[N*100];
vector<int> e[N];
int fa[N];
int rot[N];
int idx;
void modi(int &rt,int pre,int l,int r,int pos,int k){
    rt=++idx;
    tr[rt]=tr[pre];
    tr[rt].val+=k;
    if(l==r) return;
    if(pos<=mid) modi(tr[rt].ls,tr[pre].ls,l,mid,pos,k);
    else modi(tr[rt].rs,tr[pre].rs,mid+1,r,pos,k);
}
int query(int A,int B,int C,int D,int l,int r,int k){
    if(l==r) return l;
    int dta=tr[tr[A].ls].val+tr[tr[B].ls].val-tr[tr[C].ls].val-tr[tr[D].ls].val;
    if(k<=dta){
        return query(tr[A].ls,tr[B].ls,tr[C].ls,tr[D].ls,l,mid,k);
    }
    else return query(tr[A].rs,tr[B].rs,tr[C].rs,tr[D].rs,mid+1,r,k-dta);
}
int siz[N],son[N],top[N],dep[N];
void dfs(int u,int f=0){
    fa[u]=f;siz[u]=1;
    dep[u]=dep[f]+1;
    modi(rot[u],rot[f],0,inf,a[u],1);
    for(int v:e[u]){
        if(v==f) continue;
        dfs(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp){
    top[u]=tp;
    if(son[u]) dfs2(son[u],tp);
    for(int v:e[u]){
        if(v==fa[u] or v==son[u]) continue;
        dfs2(v,v);
    }
}
int LCA(int u,int v){
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]]) swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    return u;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(1);
    dfs2(1,1);
    int lst=0;
    for(int i=1;i<=m;i++){
        int u,v,k;
        cin>>u>>v>>k;
        u^=lst;
        int lca=LCA(u,v);
        cout<<(lst=query(rot[u],rot[v],rot[lca],rot[fa[lca]],0,inf,k))<<"\n";
    }
}

写的很快，然后调的也很快，事实证明我写线段树的准度还是挺高的，除去LCA没记 $dep$ 和见祖宗以外没啥问题

动态dp

前置技能：矩阵乘法、树剖/LCT、dp

模板题 P4719

给 $n$ 个点的树，点带点权，有 $m$ 次操作给定 $x,y$ 表示修改 $x$ 的权值为 $y$，每次操作后求出这棵树的最大独立集的权值大小

最大权独立集

在图/树上选若干结点使得无直接连边，称为独立集

最大权独立集就是点权和最大的独立集

不带修改

不带修怎么做

设 $dp_{i,0}$ 表示 $i$ 不在独立集时以 $i$ 为根的子树内的最大权和

同理 $dp_{i,1}$ 表示 $i$ 在独立集时的

显然有树形dp

$$dp_{u,0}=\sum_{v\in son_u} \max(dp_{v,0},dp_{v,1})\\ dp_{u,1}=val(u)+\sum_{v\in son_u} f_{v,0}$$

暴力做法

我们看方程可以发现，修改一个点的权值只会对他自己和他的祖先产生影响，于是每次修改操作实际上我们需要更改的是他到根的路径上所有点的dp值

优化

这个往上跳的过程能搞得算法一般就是俩，树剖或者倍增，这还有修改，那么相信树剖的力量吧

有一个小问题，就是树剖套的那个线段树啊，他只能维护具有结合律的信息，显然啊这个dp的递推他是不满足结合律的

能不能有一个东西，又满足结合律又可以辅助dp递推呢

诶就是矩阵

还有就是原来的方程不是很利于优化，我们要针对树剖搞一下

$$g_{u,0}=\sum_{v\in lightson_u} \max(f_{v,0},f_{v,1})\\ g_{u,1}=val(u)+\sum_{v\in lightson_u} f_{v,0}$$

好像没啥区别？

不对， $g$ 里面存的不是所有儿子，只是轻儿子的dp值

那么 $f$ 可以简化处理了(此处 $son_u$ 表示重儿砸)

$$f_{u,0}=g_{u,0}+\max(f_{son_u,0},f_{son_u,1})\\ f_{u,1}=g_{u,1}+val(u)+f_{son_u,0}$$

我们稍微做点手脚，我们不用编号来dp，我们用dfs序来dp，那么这个 $f$ 的式子又可以变形一下

$$f_{u,0}=g_{u,0}+\max(f_{u+1,0},f_{u+1,1})\\ f_{u,1}=g_{u,1}+val(u)+f_{u+1,0}$$
对于叶子，有 $f_{i,0}=0,f_{i,1}=val(i)$

于是我们可以构建一个很奇怪转移矩阵

$$\begin{bmatrix} g_{i,0}+\max(f_{i+1,0},f_{i+1,1})\\ (g_{i,1}+val(i))+f_{i+1,0} \end{bmatrix} =\begin{bmatrix} f_{i,0}\\ f_{i,1} \end{bmatrix}$$

这个矩阵好像不太对劲，我们正常的矩阵乘法貌似是用乘法和加法啊

可以证明用 $\max$ 代替乘法构建矩阵乘法一样满足结合律