Thomasguo666的小屋

首先，看到这种区间 $k$ 大值查询的题，还不强制在线，那一般可以整体二分乱搞。

如果你不会整体二分，出门右转 Dynamic Rankings（当然下面也会就这题具体说明一下）。

所以我们模拟一遍所有的修改，同时把每个修改操作改成删去一个数再加上一个数。

注意到这题是树上的问题，所以要个树链剖分。

因为我写习惯了 $k$ 小值，所以这里用 $1e8$ 减去每个权值。

然后我们用树状数组维护小于等于 $mid$ 的数有多少个。如果一个修改操作修改成的数不超过 $mid$ ，那么就执行这次操作，并且把它加到操作序列 $q_1$ 里去，否则加到 $q_2$ 里去。对于一个询问操作 ${k,l,r}$ ，如果 $[l,r]$ 中不超过 $mid$ 的数大于等于 $k$ 个，就把它放到 $q_1$ 里去，否则把 $k$ 减去不超过 $mid$ 的数的个数，再加到 $q_2$ 里去。这样 $q_1$ 与 $q_2$ 实际上变为了两个规模更小的子问题，递归处理掉就好了（当然进入下一层递归之前要把这一层递归中做的操作撤销掉）

代码：（复杂度 $O(nlog^3n)$ ）

#include <bits/stdc++.h>
#define debug printf("Running %s on line %d...\n",__FUNCTION__,__LINE__)
#define in inline
#define re register
using namespace std;
typedef long long ll;
typedef double db;
in int read()
{
    int ans=0,f=1;char c=getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=-1;
    for (;isdigit(c);c=getchar()) ans=(ans<<3)+(ans<<1)+(c^48);
    return ans*f;
}
int a[300005];
int n,m;
int head[100005],tail[200005],nex[200005];
in void addedge(int u,int v,int k)
{
    nex[k]=head[u];
    head[u]=k;
    tail[k]=v;
}
int fa[100005],sz[100005],son[100005],top[100005],l[100005],dep[100005];
void dfs1(int u)
{
    sz[u]=1;
    for (int e=head[u];e;e=nex[e])
    {
        int v=tail[e];
        if (v==fa[u]) continue;
        fa[v]=u,dep[v]=dep[u]+1;
        dfs1(v),sz[u]+=sz[v];
        if (sz[v]>sz[son[u]]) son[u]=v;
    }
}
int tot;
void dfs2(int u,int topf)
{
    top[u]=topf,l[u]=++tot;
    if (!son[u]) return;
    dfs2(son[u],topf);
    for (int e=head[u];e;e=nex[e])
    {
        int v=tail[e];
        if (v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}
struct data
{
    int l,r,v,p,id;
    data () {}
    data (int l,int r,int v,int p,int id):l(l),r(r),v(v),p(p),id(id) {}
} q[400005],q1[400005],q2[400005];
int ans[100005];
int cnt1,cnt2;
int t[400005];
void add(int x,int v)
{
    for (;x<=n;x+=x&(-x)) t[x]+=v;
}
int sum(int x)
{
    int s=0;
    for (;x;x-=x&(-x)) s+=t[x];
    return s;
}
int query(int x,int y)
{
    int ans=0;
    while (top[x]!=top[y])
    {
        if (dep[top[x]]<dep[top[y]]) swap(x,y);
        ans+=sum(l[x])-sum(l[top[x]]-1);
        x=fa[top[x]];
    }
    if (dep[x]>dep[y]) swap(x,y);
    ans+=sum(l[y])-sum(l[x]-1);
    return ans;
}
void solve(int tl,int tr,int ql,int qr)
{
    if (ql>qr) return;
    if (tl==tr)
    {
        for (int i=ql;i<=qr;i++) ans[q[i].id]=tl;
        return ;
    }
    int mid=tl+tr>>1,j=0,k=0;
    for (int i=ql;i<=qr;i++)
    {
        if (!q[i].id)
        {
            if (q[i].v<=mid)
            {
                add(l[q[i].l],q[i].p);
                q1[++j]=q[i];
            }
            else q2[++k]=q[i];
        }
        else
        {
            int s=query(q[i].l,q[i].r);
            if (s<q[i].v) q[i].v-=s,q2[++k]=q[i];
            else q1[++j]=q[i];
        }
    }
    for (int i=1;i<=j;i++) if (!q1[i].id) add(l[q1[i].l],-q1[i].p); 
    for (int i=1;i<=j;i++) q[ql+i-1]=q1[i];
    for (int i=1;i<=k;i++) q[ql+i+j-1]=q2[i];
    solve(tl,mid,ql,ql+j-1),solve(mid+1,tr,ql+j,qr);
}
int main()
{
    n=read(),m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    for (int i=1;i<n;i++)
    {
        int u=read(),v=read();
        addedge(u,v,i<<1);
        addedge(v,u,i<<1|1);
    }
    dfs1(1);
    dfs2(1,0);
    for (int i=1;i<=n;i++) q[++cnt1]=data(i,0,1e8-a[i],1,0);
    for (int i=1;i<=m;i++)
    {
        int k=read(),l=read(),r=read();
        if (k)
        {
            q[++cnt1]=data(l,r,k,0,++cnt2);
        }
        else
        {
            q[++cnt1]=data(l,0,1e8-a[l],-1,0);
            q[++cnt1]=data(l,0,1e8-(a[l]=r),1,0);
        }
    }
    solve(0,1e8,1,cnt1);
    for (int i=1;i<=cnt2;i++) ((1e8-ans[i])?cout<<int(1e8-ans[i])<<endl:cout<<"invalid request!"<<endl);
    return 0;
}