Accepted/107880K/3020MS

bzoj1146.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
const int maxn=100005,maxk=8000005;
int w[maxn],a[maxn],b[maxn],c[maxn],san[maxn],A[maxn],B[maxn];
int C[maxn],vis[maxn],lca[maxn],lft[maxn],rht[maxn];
int first[maxn],fa[maxn],f[maxn],rt[maxn];
int sum[maxk],ls[maxk],rs[maxk];
int n,m,tot,cnt,ne,Tot,tim,numa,numb;
vector <int> e[maxn];
vector <pair<int,int> >ask[maxn];
typedef vector<int>::iterator ii;
typedef vector<pair<int,int> >::iterator pii;
void update(int l,int r,int x,int k){
    sum[++Tot]=sum[x]+k;
    ls[Tot]=l;rs[Tot]=r;
}
int lowbit(int x){
    return x&(-x);
}
int edit(int x,int l,int r,int y,int k){
    if (l==r){
        update(0,0,x,k);
        return Tot;
    }
    int m=(l+r)/2;
    if (y<=m){
        ne=edit(ls[x],l,m,y,k);
        update(ne,rs[x],x,k);
    }else{
        ne=edit(rs[x],m+1,r,y,k);
        update(ls[x],ne,x,k);
    }
    return Tot;
}
int find(int x){
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
void dfs(int x){
    rt[x]=edit(rt[f[x]],1,tot,w[x],1);
    lft[x]=++tim;fa[x]=x;
    for (ii i=e[x].begin();i!=e[x].end();i++){
        if (*i!=f[x]){
            f[*i]=x;
            dfs(*i);
            fa[*i]=x;
        }
    }
    rht[x]=tim;
    vis[x]=1;
    for (pii i=ask[x].begin();i!=ask[x].end();i++)
        if (vis[i->first])
            lca[i->second]=find(i->first);
}
void bitup(int x,int pos,int k){
    for (;x<=n;x+=lowbit(x))
        c[x]=edit(c[x],1,tot,pos,k);
}
void get(int x,int p){
    if (p){
        a[numa++]=rt[x];
        x=lft[x];
        for (;x;x-=lowbit(x))
            a[numa++]=c[x];
    }else{
        b[numb++]=rt[x];
        x=lft[x];
        for (;x;x-=lowbit(x))
            b[numb++]=c[x];
    }
}
int query(int *a,int numa,int *b,int numb,int k){
    int t,tt,l=1,r=tot;
    while (l<r){
        t=tt=0;
        for (int i=0;i<numa;i++){
            t+=sum[rs[a[i]]];
            tt+=sum[a[i]];
        }
        for (int i=0;i<numb;i++){
            t-=sum[rs[b[i]]];
            tt-=sum[b[i]];
        }
        if (tt<k)
            return -1;
        if (k<=t){
            for (int i=0;i<numa;i++)
                a[i]=rs[a[i]];
            for (int i=0;i<numb;i++)
                b[i]=rs[b[i]];
            l=(l+r)/2+1;
        }else{
            for (int i=0;i<numa;i++)
                a[i]=ls[a[i]];
            for (int i=0;i<numb;i++)
                b[i]=ls[b[i]];
            r=(l+r)/2;
            k-=t;
        }
    }
    return l;
}
int main(){
    int x,y,mid;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d",&w[i]);
        san[++tot]=w[i];
    }
    for (int i=1;i<n;i++){
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&A[i],&B[i],&C[i]);
        if (!A[i])
            san[++tot]=C[i];
        else{
            ask[B[i]].push_back(make_pair(C[i],i));
            ask[C[i]].push_back(make_pair(B[i],i));
        }
    }
    sort(&san[1],&san[tot+1]);
    tot=unique(&san[1],&san[tot+1])-&san[1];
    for (int i=1;i<=n;i++)
        w[i]=lower_bound(&san[1],&san[tot+1],w[i])-&san[0];
    dfs(1);
    for (int i=1;i<=n;i++)
        c[i]=rt[0];
    for (int i=1;i<=m;i++){
        if (A[i]){
            x=B[i];y=C[i];mid=lca[i];
            numa=numb=0;
            get(x,1);get(y,1);
            get(mid,0);get(f[mid],0);
            x=query(a,numa,b,numb,A[i]);
            if (x<0)
                printf("invalid request!\n");
            else
                printf("%d\n",san[x]);
        }else{
            x=B[i];y=C[i];
            y=lower_bound(&san[1],&san[tot+1],y)-&san[0];
            bitup(lft[x],w[x],-1);
            bitup(rht[x]+1,w[x],1);
            bitup(lft[x],y,1);
            bitup(rht[x]+1,y,-1);
            w[x]=y;
        }
    }
    return 0;
}