P4175 题解

· · 个人记录

经典题目动态区间第 k 大上树版本。

三只 \log：重链剖分 + 树状数组 + 主席树。

两只 \log：树上差分 + 主席树套树状数组。

代码是两只 \log 的。

#include <bits/stdc++.h>

// 缺省源

using namespace std;

const int MAXN=1000005;

vector<int> E[MAXN];
int n,N,q,a[MAXN],b[MAXN],c[MAXN],d[MAXN],e[MAXN];
int dfn[MAXN],dep[MAXN],siz[MAXN],f[MAXN][17],tot=0;

int rt[MAXN],tr[30000005],ls[30000005],rs[30000005],t0t=0;

void dfs(int u,int fa){
    f[u][0]=fa; dfn[u]=++t0t; dep[u]=dep[fa]+1; siz[u]=1;
    for(int v:E[u]) if(v!=fa) dfs(v,u),siz[u]+=siz[v];
}

struct Node{int x,y,z;};
int LCA(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    int tmp=dep[u]-dep[v];
    for(int j=0;j<17;j++) if(tmp>>j&1) u=f[u][j];
    if(u==v) return u;
    for(int j=16;j>=0;j--) if(f[u][j]!=f[v][j]) u=f[u][j],v=f[v][j];
    return f[u][0];
}

vector<int> vec1,vec2;

void upd(int &p,int l,int r,int t,int k){
    if(!p) p=++tot;
    if(l==r) return tr[p]+=k,void();
    int mid=(l+r)>>1;
    if(t<=mid) upd(ls[p],l,mid,t,k);
    else upd(rs[p],mid+1,r,t,k);
    tr[p]=tr[ls[p]]+tr[rs[p]];
}
int query(int l,int r,int k){
    if(l==r) return l;
    int sum1=0,sum2=0,mid=(l+r)>>1;
    for(int i:vec1) sum1+=tr[rs[i]];
    for(int i:vec2) sum2+=tr[rs[i]];
    if(sum1-sum2>=k){
        for(int i=0;i<vec1.size();i++) vec1[i]=rs[vec1[i]];
        for(int i=0;i<vec2.size();i++) vec2[i]=rs[vec2[i]];
        return query(mid+1,r,k);
    }else{
        for(int i=0;i<vec1.size();i++) vec1[i]=ls[vec1[i]];
        for(int i=0;i<vec2.size();i++) vec2[i]=ls[vec2[i]];
        return query(l,mid,k-(sum1-sum2));
    }
}

inline int lowbit(int x){return x&(-x);}
void add(int x,int t,int k){for(int i=x;i<=n;i+=lowbit(i)) upd(rt[i],0,N,t,k);}
int qry1(int x){for(int i=x;i;i-=lowbit(i)) vec1.push_back(rt[i]);}
int qry2(int x){for(int i=x;i;i-=lowbit(i)) vec2.push_back(rt[i]);}
int Sum(){
    int ans=0;
    for(int i:vec1) ans+=tr[i];
    for(int i:vec2) ans-=tr[i];
    return ans;
}

void put(string s){for(int i=0;i<s.size();i++) pc(s[i]);}

int main(){
    int t=0; read(n,q);
    for(int i=1;i<=n;i++) read(a[i]),b[++t]=a[i];
    for(int i=1;i<n;i++){
        int u,v; read(u,v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    for(int i=1;i<=q;i++){
        read(c[i],d[i],e[i]);
        if(!c[i]) b[++t]=e[i];
    }
    sort(b+1,b+1+t);
    t=unique(b+1,b+1+t)-b-1; N=t+100000;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+t,a[i])-b;
    for(int i=1;i<=q;i++) if(!c[i]) e[i]=lower_bound(b+1,b+1+t,e[i])-b;

    dfs(1,0); tot=0;
    for(int j=1;j<17;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=n;i++) add(dfn[i],a[i],1),add(dfn[i]+siz[i],a[i],-1);

    for(int i=1;i<=q;i++){
        if(c[i]){
            int L=LCA(d[i],e[i]),X=d[i],Y=e[i];
            vec1.clear(),vec2.clear();
            qry1(dfn[X]),qry1(dfn[Y]);
            qry2(dfn[L]),qry2(dfn[f[L][0]]);
            if(Sum()<c[i]) cout<<"invalid request!\n";
            else cout<<b[query(0,N,c[i])]<<'\n';
        }else{
            add(dfn[d[i]],a[d[i]],-1);
            add(dfn[d[i]]+siz[d[i]],a[d[i]],1);
            add(dfn[d[i]],a[d[i]]=e[i],1);
            add(dfn[d[i]]+siz[d[i]],a[d[i]],-1);
        }
    }
    return flush(),0;
}