洛谷省选Day1T3観波加奈(树链剖分+BIT+平衡树)

题解

  mdzz写fhqtreap被卡常了T_T,死活卡不过,先留坑吧
  吼题!在树上每一个点下挂一棵平衡树,只维护轻儿子的权值,查第kk大的时候,把自己,重儿子和父亲丢进平衡树查第k大,查完再删掉就好了。
  因为每条重链上只有重链头是轻儿子,所以每次链加的时候我们只需要单点修改重链头父亲的平衡树,所以复杂度是O(nlog2n)O(nlog^2n)的。
  考虑怎么优化。实际上我们只有在查询的时候才需要更新轻儿子的信息,所以每次修改的时候只在父亲记录一下需要修改的儿子,下一次询问的时候再更新,可以证明复杂度均摊下来是O(nlogn)O(nlogn)的。大概就是某次操作复杂度为O(x)O(x),那么一定需要O(x)O(x)次操作,例如这次查询的复杂度为O(x)O(x),那么之前一定耗费过O(x)O(x)的时间进行链加的操作,所以就证明了这么做是O(nlogn)O(nlogn)的了。

代码

// luogu-judger-enable-o2
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#define lt poitree[x].ls
#define rt poitree[x].rs
using namespace std;
const int maxn=1000010, inf=1e9;
struct poi{int ls, rs, size, sum, rnd, fa;}poitree[maxn<<2];
struct edge{int too, pre;}e[maxn<<1];
vector<int>v[maxn];
int n, m, tot, tott, x, y, ty, z, cnt;
int last[maxn], size[maxn], fa[maxn], son[maxn], top[maxn], l[maxn], r[maxn], tree[maxn];
int pos[maxn], root[maxn], a[maxn], dep[maxn];
bool vis[maxn];
char buf[80000010],*ptr=buf-1;
inline int read(int &k)
{
    char c=*++ptr; k=0;
    while(c<48||c>57)c=*++ptr;
    while(c>=48&&c<=57){k=k*10+c-'0';c=*++ptr;}
    return k;
}
inline void add(int x, int y){e[++tot]=(edge){y, last[x]}; last[x]=tot;}
inline void poibuild(int x, int delta) 
{
    poitree[x].rnd=rand()<<15|rand(); 
    poitree[x].sum=delta;
    poitree[x].size=1;
    poitree[x].fa=lt=rt=0;
}
inline void poiup(int x) 
{
    if(!x) return; 
    poitree[x].size=poitree[lt].size+poitree[rt].size+1;
    poitree[lt].fa=x; poitree[rt].fa=x;
}
void merge(int &x, int l, int r)
{
    if(!l || !r) x=l+r;
    else if(poitree[l].rnd<poitree[r].rnd) x=l, merge(poitree[x].rs, poitree[x].rs, r), poiup(x);
    else x=r, merge(poitree[x].ls, l, poitree[x].ls), poiup(x);
}
void split(int x, int &l, int &r, int k)
{
    if(!k) l=0, r=x;
    else if(k==poitree[x].size) l=x, r=0;
    else if(k<=poitree[lt].size) r=x, split(lt, l, lt, k), poiup(x);
    else l=x, split(rt, rt, r, k-poitree[lt].size-1), poiup(x);
}
int qzrank(int x, int w)
{
    int tmp=0;
    while (x) {
        if(poitree[x].sum>=w) x=lt;
        else tmp+=poitree[lt].size+1,x=rt;
    }
    return tmp;
}
int rank(int x)
{
    int fa=poitree[x].fa,tmp=0;
    while (fa) {
        if(poitree[fa].rs==x) tmp+=poitree[poitree[fa].ls].size+1;
        x=fa; fa=poitree[x].fa;
    }
    return tmp;
}
inline void poiadd(int x, int y)
{
    int rk=qzrank(root[x], poitree[y].sum)+1;
    int X, Y;
    split(root[x], X, Y, rk-1);
    merge(root[x], X, y);
    merge(root[x], root[x], Y);
}
inline void poidel(int x, int y)
{
    poitree[root[x]].fa=0;
    int fa=poitree[y].fa;
    int tmp; merge(tmp, poitree[y].ls, poitree[y].rs);
    if(y==root[x]) root[x]=tmp;
    poitree[tmp].fa=fa;
    if(poitree[fa].ls==y) poitree[fa].ls=tmp;
    else poitree[fa].rs=tmp;
    int p=fa; while(p) poiup(p), p=poitree[p].fa;
    poitree[y].ls=poitree[y].rs=0; poitree[y].size=1;
}
void dfs1(int x)
{
    size[x]=1;
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa[x])
    {
        fa[too]=x; dep[too]=dep[x]+1;
        dfs1(too);
        size[x]+=size[too];
        if(size[son[x]]<size[too]) son[x]=too;
    }
}
void dfs2(int x, int tp)
{
    top[x]=tp; l[x]=++tott;
    if(son[x]) dfs2(son[x], tp);
    for(int i=last[x], too;i;i=e[i].pre)
    if((too=e[i].too)!=fa[x] && too!=son[x]) 
    {
        poiadd(x, too);
        dfs2(too, too);
    }
    r[x]=tott;
}
inline void update(int x, int delta){for(;x<=n;x+=x&-x) tree[x]+=delta;}
inline int query(int x){int sum=0; for(;x;x-=x&-x) sum+=tree[x]; return sum;}
inline int solve(int x, int y)
{
    int f1=top[x], f2=top[y];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2]) swap(x, y), swap(f1, f2);
        v[fa[f1]].push_back(f1);
        x=fa[f1]; f1=top[x];
    }
    if(dep[x]<dep[y]) swap(x, y);
    if(y==top[y]) v[fa[y]].push_back(y);
    return y;
}
inline int queryans(int x, int k)
{
    poibuild(n+1, query(r[x])-query(l[x]-1)); poiadd(x, n+1);
    if(fa[x]) poibuild(n+2, query(r[fa[x]])-query(l[fa[x]]-1)), poiadd(x, n+2);
    if(son[x]) poibuild(n+3, query(r[son[x]])-query(l[son[x]]-1)), poiadd(x, n+3);
    for(int i=0;i<v[x].size();i++)
    if(!vis[v[x][i]])
    {
    	cnt++;
        vis[v[x][i]]=1;
   		poidel(x, v[x][i]); 
        poitree[v[x][i]].sum=query(r[v[x][i]])-query(l[v[x][i]]-1);
   		poiadd(x, v[x][i]);
    }
    for(int i=0;i<v[x].size();i++) vis[v[x][i]]=0; v[x].clear();
    int X, Y, Z; split(root[x], X, Y, k); 
    split(X, Z, X, k-1);
    int ans=poitree[X].sum;  
    merge(root[x], Z, X); merge(root[x], root[x], Y);    
    poidel(x, n+1); 
    if(fa[x]) poidel(x, n+2); if(son[x]) poidel(x, n+3);
    return ans;
}
int main()
{
    fread(buf,1,sizeof(buf),stdin); srand(23333333);
   	read(n); read(m); poitree[0].rnd=(rand()<<15)|rand(); poitree[0].sum=inf;
    for(int i=1;i<=n;i++) read(a[i]), poibuild(i, a[i]);
    for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x);
    dfs1(1); dfs2(1, 1); 
    tree[1]=a[1]; for(int i=2;i<=n;i++) tree[l[i]]+=a[i], tree[l[fa[i]]]-=a[i];
    for(int i=1;i<=n;i++) if(i+(i&-i)<=n) tree[i+(i&-i)]+=tree[i];
    for(int i=1;i<=m;i++)
    {
        read(ty); read(x), read(y);
        if(ty==1) 
        {
            int lca=solve(x, y); read(z);
            update(l[x], z); update(l[y], z); update(l[lca], -z);
            if(fa[lca]) update(l[fa[lca]], -z);
        }
        else printf("%d\n", queryans(x, y));
    }
}