【Ynoi2012】D2T3

foreverlasting · 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;
}