自动搬运

查看原文

来自洛谷，原作者为

	foreverlasting 果然，失去别人远比自己离去更加令人恐惧。

搬运于2025-08-24 22:09:26，当前版本为作者最后更新于2019-05-25 08:48:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

推销博客

一道思路简单的卡常题。

首先两个$log$的做法非常简单，你就重链剖分一下，然后维护每个点的轻儿子的平衡树，每次查询的时候只用把这个点的重儿子和父亲和它自己加进平衡树就可以了。这样的话，修改是$O(log^2n)$，查询是$O(logn)$的。但事实上查询的时候常数有$6$，所以这样只能跑到$80$分。

接下来就分成两条路。

第一种是正解的卡常方法，每个点维护七八个重儿子，这样修改的复杂度就可以除以$7$,$8$左右，查询乘上$7$,$8$左右，这样就可以跑过去了。

（听说有一个$log$的做法，暂时还不会）

第二种是我的卡常方法。首先我原本写的是$fhq treap$，然后换成了$treap$，一下子跑过了两个点。然后每次查询的时候我也不去插入再删除，直接大力分类讨论，这样就只有查询$k$，$k-1$，$k-2$，$k-3$了。一下子常数减小，跑得贼快。

code:

//2019.5.25 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-10
#define RG register
#define db double
#define pc(x) __builtin_popcount(x)
typedef pair<int,int> Pair;
#define mp make_pair
#define fi first
#define se second
#define gc getchar
//inline char gc() {
//    static char buf[100000],*p1,*p2;
//    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
//}
inline int read() {
    res s=0,ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
    return s;
}
//inline LL Read() {
//    RG LL s=0;
//    res ch=gc();
//    while(ch<'0'||ch>'9')ch=gc();
//    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=gc();
//    return s;
//}
inline void swap(res &x,res &y) {
    x^=y^=x^=y;
}
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N=1e6+10;
namespace MAIN {
    struct E{
        int next,to;
        E() {}
        E(res next,res to):next(next),to(to) {}
    }edge[N<<1];
    int head[N],cnt;
    inline void addedge(const res &u,const res &v){
        edge[++cnt]=E(head[u],v),head[u]=cnt;
        edge[++cnt]=E(head[v],u),head[v]=cnt;
    }
    int n,m;
    int fa[N],dep[N],top[N],sz[N],son[N],dfn[N],idx;
    void dfs(res x,res fax,res depx){
        dep[x]=depx,sz[x]=1,fa[x]=fax;
        for(res i=head[x];~i;i=edge[i].next){
            res tox=edge[i].to;
            if(tox==fax)continue;
            dfs(tox,x,depx+1),sz[x]+=sz[tox];
            if(sz[son[x]]<sz[tox])son[x]=tox;
        }
    }
    struct Treap{
        int pri,sz,son[2],val,cnt;
    }tr[N];
    int st[N],Top,tot,rt[N];
    inline int newnode(const res &val){
        res p=Top?st[Top--]:++tot;
        tr[p].val=val,tr[p].sz=tr[p].cnt=1,tr[p].son[0]=tr[p].son[1]=0;
        return p;
    }
    inline void pushup(const res &x){
        res ls=tr[x].son[0],rs=tr[x].son[1];
        tr[x].sz=tr[ls].sz+tr[rs].sz+tr[x].cnt;
    }
    inline void rotate(res &x,const res &d){
        res y=tr[x].son[d];
        tr[x].son[d]=tr[y].son[d^1],tr[y].son[d^1]=x,pushup(x),pushup(x=y);
    }
    void insert(res &x,const res &val){
        if(!x){x=newnode(val);return;}
        tr[x].sz++;
        if(val==tr[x].val)tr[x].cnt++;
        else {
            res d=(tr[x].val<val);
            insert(tr[x].son[d],val);
            if(tr[x].pri>tr[tr[x].son[d]].pri)rotate(x,d);
        }
    }
    void del(res &x,const res &val){
        if(!x)return;
        if(tr[x].val==val){
            if(tr[x].cnt>1)tr[x].cnt--,tr[x].sz--;
            else {
                res ls=tr[x].son[0],rs=tr[x].son[1];
                if(!ls||!rs)st[++Top]=x,x=ls|rs;
                else rotate(x,tr[ls].pri>tr[rs].pri),del(x,val);
            }
            return;
        }
        tr[x].sz--,del(tr[x].son[tr[x].val<val],val);
    }
    inline int rankget(res RT,res k){
        while(233){
            if(tr[tr[RT].son[0]].sz+1<=k&&k<=tr[tr[RT].son[0]].sz+tr[RT].cnt)return tr[RT].val;
            if(k<=tr[tr[RT].son[0]].sz)RT=tr[RT].son[0];
            else k-=tr[tr[RT].son[0]].sz+tr[RT].cnt,RT=tr[RT].son[1];
        }
    }
    int val[N];
    void dfs(res x,res topx){
        dfn[x]=++idx,top[x]=topx;
        if(son[x])dfs(son[x],topx);
        for(res i=head[x];~i;i=edge[i].next){
            res tox=edge[i].to;
            if(tox==fa[x]||tox==son[x])continue;
            insert(rt[x],val[tox]),dfs(tox,tox);
        }
    }
    int T[N];
#define lowbit(x) (x&-x)
    inline void modify(res x,res y){
        for(res i=x;i<=n;i+=lowbit(i))T[i]+=y;
    }
    inline int query(res x){
        res ret=0;
        for(res i=x;i;i-=lowbit(i))ret+=T[i];
        return ret;
    }
    inline void Modify(res x,res va){
        del(rt[fa[x]],val[x]),val[x]+=va,insert(rt[fa[x]],val[x]);
    }
    inline void modify(res u,res v,res va){
        while(top[u]!=top[v]){
            if(dep[top[u]]<dep[top[v]])swap(u,v);
            Modify(top[u],va),modify(dfn[top[u]],va),modify(dfn[u]+1,-va),u=fa[top[u]];
        }
        if(dep[u]>dep[v])swap(u,v);
        if(top[u]==u&&u!=1)Modify(u,va);
        modify(dfn[u],va),modify(dfn[v]+1,-va);
    }
    int a[N],tmp[10];
    inline void MAIN(){
        n=read(),m=read();
        for(res i=1;i<=n;i++)a[i]=val[i]=read(),head[i]=-1,tr[i].pri=rand();
        tr[n+1].pri=rand(),tr[n+2].pri=rand(),tr[n+3].pri=rand();
        for(res i=1;i<n;i++){
            res u=read(),v=read();
            addedge(u,v);
        }
        dfs(1,0,1),dfs(1,1);
        while(m--){
            res opt=read();
            if(opt==1){
                res x=read(),y=read(),z=read();
                modify(x,y,z);
            }
            else {
                res x=read(),y=read(),cnt=0;
                if(y<=tr[rt[x]].sz)tmp[++cnt]=rankget(rt[x],y);
                if(y>1&&y-1<=tr[rt[x]].sz)tmp[++cnt]=rankget(rt[x],y-1);
                if(y>2&&y-2<=tr[rt[x]].sz)tmp[++cnt]=rankget(rt[x],y-2);
                if(y>3&&y-3<=tr[rt[x]].sz)tmp[++cnt]=rankget(rt[x],y-3);
                tmp[++cnt]=a[x]+query(dfn[x]);
                if(fa[x])tmp[++cnt]=a[fa[x]]+query(dfn[fa[x]]);
                if(son[x])tmp[++cnt]=a[son[x]]+query(dfn[son[x]]);
                sort(tmp+1,tmp+cnt+1);
                if(y<=3)printf("%d\n",tmp[y]);
                else printf("%d\n",tmp[4]);
            }
        }
    }
}
int main() {
    srand((unsigned)time(NULL));
//    freopen("zao.in","r",stdin);
//    freopen("std.out","w",stdout);
    MAIN::MAIN();
    return 0;
}