线段树合并：从入门到退役

DS 线段树

你以为是学习笔记，其实是刷题记录

雨天的尾巴

每个点维护 $mx$ 表示权值线段树的最大值， $id$ 表示最大值位置，修改利用差分处理即可

[USACO17JAN] Promotion Counting P

我们注意到原问题就是个偏序问题，用线段树合并从下往上维护区间和即可

[POI2011] ROT-Tree Rotations

考虑偏序问题怎么处理，注意到线段树的结构其实是天生的分治，于是搞就行了，权值线段树，边读入边处理即可

Blood Cousins

以深度为下标，把询问挂在 $k$ 级祖先上面，然后就是单点查询权值线段树的简单线段树合并了

[Cnoi2019] 雪松果树

居然是上一题的双倍经验！

等等我怎么TM了

MLE解决方案：写个栈垃圾回收一下就好了，线段树合并会产生大量无用结点

TLE：不怎么需要卡常，快读就差不多了

放一下代码吧确实比较扯 $10^6$ 就把我卡了，果然垃圾回收好习惯

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int rd(){
    int a=0,c=getchar(),s=0;
    while(!isdigit(c)) s|=(c=='-'),c=getchar();
    while(isdigit(c)) a=a*10+c-48,c=getchar();
    return s?-a:a;
}
int son[N],fa[N];
int dep[N];
int siz[N];
int top[N];
vector<int> S[N];
int n,m;
int rt;
int dfn[N],rev[N];
void dfs1(int u){
    dep[u]=dep[fa[u]]+1;
    siz[u]=1;
    for(int v:S[u]){
        dfs1(v);
        siz[u]+=siz[v];
        if(siz[son[u]]<siz[v]) son[u]=v; 
    }
}
int DFN;
void dfs2(int u,int tp){
    top[u]=tp;
    dfn[u]=++DFN;
    rev[DFN]=u;
    if(son[u]) dfs2(son[u],tp);
    for(int v:S[u]){
        if(v==son[u]) continue; 
        dfs2(v,v);
    }
}
int jump(int x,int k){//k祖先
    int temp=dep[x]-k;
    while(dep[top[x]]>temp) x=fa[top[x]];
    temp=dep[x]-temp;
    return rev[dfn[x]-temp];
}
struct requ{
    int k;
    int id;
};
vector<requ> Q[N];
int ans[N];
struct node{
    int ls,rs;
    int val;
}tr[N*4];
int idx;
stack<int,vector<int> > rbish;
inline int nw(){
    int tmp;
    if(!rbish.empty()) tmp=rbish.top(),rbish.pop();
    else tmp=++idx;
    tr[tmp]={0,0,0};
    return tmp;
}
int rot[N];
void add(int &rt,int l,int r,int pos){
    if(!rt) rt=nw();
    if(l==r){
        tr[rt].val++;
        return;
    }
    if(pos<=(l+r>>1)) add(tr[rt].ls,l,(l+r>>1),pos);
    else add(tr[rt].rs,(l+r>>1)+1,r,pos);
}
int query(int &rt,int l,int r,int pos){
    // if(!rt) return 0;
    if(l==r) return tr[rt].val;
    if(pos<=(l+r>>1)) return query(tr[rt].ls,l,(l+r>>1),pos);
    else return query(tr[rt].rs,(l+r>>1)+1,r,pos);
}
int mg(int x,int y,int l,int r){
    if(!x or !y) return x|y;
    if(l==r){
        tr[x].val+=tr[y].val;
        return x;
    }   
    tr[x].ls=mg(tr[x].ls,tr[y].ls,l,(l+r>>1));
    tr[x].rs=mg(tr[x].rs,tr[y].rs,(l+r>>1)+1,r);
    rbish.push(y);
    return x;
}
void dfs(int u){
    for(int v:S[u]){
        dfs(v);
        rot[u]=mg(rot[u],rot[v],1,n+1);
    }
    add(rot[u],1,n+1,dep[u]);
    for(auto q:Q[u]){
        ans[q.id]=query(rot[u],1,n+1,q.k)-1;
    }
}
int main(){
    n=rd(),m=rd();
    for(int i=2;i<=n;i++){
        fa[i]=rd();
        S[fa[i]].push_back(i);
    }   
    dfs1(1);
    dfs2(1,1);
    for(int i=1;i<=m;i++){
        int v,p;
        v=rd(),p=rd();
        if(dep[v]<=p){ans[i]=0;continue;}
        v=jump(v,p);
        p=dep[v]+p;
        //此时询问转化成 v子树内深度（总深度）为p的点的个数（记得减1）
        Q[v].push_back({p,i});
    }
    //
    dfs(1);
    for(int i=1;i<=m;i++) printf("%d ",ans[i]);
}

[湖南集训] 更为厉害

题外话：本题原名谈笑风生，后貌似因为zz原因改名，本题曾经学长讲过但是当时太菜了听不下去（现在也菜）

本题写详细思路，因为不是经验也不是很水的样子

sol

我们首先可以注意到这个三元组其实挺蠢的，其实是二元组的，因为 $a$ 定好了

其次， $a,b,c$ 之间都有祖先后代关系，并且 $a,b$ 都是 $c$ 的祖先

我们分两种情况考虑：

$b$ 是 $a$ 祖先

这种情况是简单的，我们直接数祖先和 $k$ 取 $\min$ 再数子树一乘就行了，一遍大法师随便搞

$a$ 是 $b$ 祖先

此时问题变为了 $a$ 的一个子树问题了

答案等价于 $a$ 的所有 $k$ 以下儿子的对应子树大小的和

线段树维护深度即可，合并就好

为了实现简便，我们把 $a=b$ 的情况放在第二种情况一起计算

好像还是水题，那没事了，不理解题解合并的时候开新点的意义何在，没有强制在线那样太白给

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
#define int long long
int rd(){
    int a=0,s=0,c=getchar_unlocked();
    while(!isdigit(c)) s|=(c=='-'),c=getchar_unlocked();
    while(isdigit(c)) a=a*10+c-48,c=getchar_unlocked();
    return s?-a:a;
}
int n,q;
vector<int> e[N];
int dep[N],siz[N],fa[N];
void dfs1(int u,int f){
    dep[u]=dep[f]+1;
    siz[u]=1;
    fa[u]=f;
    for(int v:e[u]){
        if(v==f) continue;
        dfs1(v,u);
        siz[u]+=siz[v];
    }
}
int ans[N];
struct qu{
    int k,id;
};
vector<qu> Q[N];
int rot[N];
struct node{
    int ls,rs,sum;
}tr[N*50];
#define lc tr[rt].ls
#define rc tr[rt].rs
#define mid (l+r>>1)
int idx;
void pushup(int rt){
    tr[rt].sum=tr[lc].sum+tr[rc].sum;
}
void add(int &rt,int l,int r,int pos,int k){
    if(!rt) rt=++idx;
    if(l==r){
        tr[rt].sum+=k;
        return;
    }
    if(pos<=mid) add(lc,l,mid,pos,k);
    else add(rc,mid+1,r,pos,k);
    pushup(rt);
}
int query(int rt,int l,int r,int L,int R){
    if(!rt or r<L or R<l) return 0;
    if(L<=l and r<=R) return tr[rt].sum;
    return query(lc,l,mid,L,R)+query(rc,mid+1,r,L,R);
}
int mg(int x,int y,int l,int r){
    if(!x or !y) return x|y;
    tr[x].sum+=tr[y].sum;
    if(l==r){
        return x;
    }
    tr[x].ls=mg(tr[x].ls,tr[y].ls,l,mid);
    tr[x].rs=mg(tr[x].rs,tr[y].rs,mid+1,r);
    pushup(x);
    return x;
}
void dfs(int u){
    for(int v:e[u]){
        if(v==fa[u]) continue;
        dfs(v);
        rot[u]=mg(rot[u],rot[v],1,n);
    }
    add(rot[u],1,n,dep[u],siz[u]-1);
    for(qu V:Q[u]){
        ans[V.id]+=query(rot[u],1,n,dep[u]+1,dep[u]+V.k);
    }
}
signed main(){
    n=rd(),q=rd();
    for(int i=1;i<n;i++){
        int u=rd(),v=rd();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dep[0]=0;
    dfs1(1,0);
    for(int i=1;i<=q;i++){
        int p=rd(),k=rd();
        Q[p].push_back({k,i});
        ans[i]+=min(dep[p]-1,k)*(siz[p]-1);
    }
    dfs(1);
    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

CF570D

状压，线段树维护深度，合并