我们发现本题只与每个数的相对大小有关，故每次操作开始前先将点权离散化，以下不再赘述。
原 std 做法
Subtask #1
暴力做法。
直接维护这个序列显然不可行，遂考虑用桶来维护，记录 $D$ 序列中每个值的出现次数。
操作 1 就是把 $x$ 到 $y$ 的简单路径上的点的点权对应的出现次数 $+k$；操作 2 求出桶内元素总和即为 $D$ 序列的元素个数，遍历找到中位数即可；操作 3 就是将桶内每个数 $\times 2$。
时间复杂度 $\mathcal{O}(nm)$。
Subtask #2
保证给定的树是一条链。
考虑将其转换成一个序列然后分块维护。对于整体的块，维护其在序列中出现的次数，对于不是整体的块，单点加到线段树上，线段树二分时枚举每个块计算贡献即可。
时间复杂度 $\mathcal{O}(m \sqrt n\log n)$。
Subtask #3
考虑先求出这颗树的括号序，在每个点第一次出现的位置执行插入点权的操作，第二次出现的位置执行删除点权的操作，这样操作 1 就变成对区间操作 $k$ 次了。
无约束条件
被选手单根号做法爆标了。/kk
对括号序和值域分块，散块修改直接暴力维护，整块修改先预处理出执行前 $i$ 个块的操作后，第 $j$ 个值域块的数量变化值，这样可以求出每个值域块内的数量，查询操作即为从小到大查找每个值域块，但是块内具体的值还不知道，再预处理出执行第 $i$ 个块的操作后值为 $j$ 的块的数量变化值，给中间每个块打上操作 $k$ 次的标记，查询找到具体的值域块后枚举块内的每个值，再枚举每个序列块加上修改的值即可。
操作 3 相当于给所有值乘 $2$，但是不好直接维护，考虑将乘法转化为除法，在操作 1 时预先计算这条路径最终会被插入的次数，比如总共有 $n$ 次操作 3，当前已经执行了 $x$ 次，如果操作 1 要将一条路径插入 $k$ 次，那么最终只需要插入 $2 ^ {n-x} \times k$ 次，查询操作就只需要将所有的数除以 $2^{n-x}$ 即可。
序列和值域块长分别取 $n^{\frac{2}{3}}$ 和 $n ^ \frac{1}{3}$，时间复杂度 $\mathcal{O}(n^{\frac{5}{3}})$。
Code
#include<bits/stdc++.h>
#define ll long long
#define deb(x) cerr<<"deb:"<<__LINE__<<" "<<#x<<"="<<x<<"\n"
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
char buf[1<<21],*p1=buf,*p2=buf;
inline int read()
{
int sum=0;char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c)){sum=(sum<<1)+(sum<<3)+(c^48);c=getchar();}
return sum;
}
const int kc1=1200,kc2=40;
int c[100100],ls[100100],sz,ch[200100],cnt,st[100100],ed[100100],fa[100100][20],dis[100100],q[100100][4];
int nks1[200100],nks2[200100],nkf1[200100][2],nkf2[200100][2];
ll qz[210][4010],al[210][100100],fk1[210],fk2[4010],s[100100];
vector<int> l[100100];
void dfs(int x,int f)
{
dis[x]=dis[f]+1;
fa[x][0]=f;
for(int i=1;i<=17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
ch[++cnt]=c[x];
st[x]=cnt;
for(auto v:l[x])
{
if(v==f)continue;
dfs(v,x);
}
ch[++cnt]=-c[x];
ed[x]=cnt;
}
int lca(int x,int y)
{
if(dis[x]<dis[y])x^=y^=x^=y;
for(int i=17;i>=0;i--)
{
if(dis[fa[x][i]]>=dis[y])x=fa[x][i];
}
if(x==y)return x;
for(int i=17;i>=0;i--)
{
if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
}
return fa[x][0];
}
void Add(int l,int r,ll k)
{
if(l>r)return;
int k1=nks1[l],k2=nks1[r];
if(k1==k2)
{
for(int i=l;i<=r;i++)
{
if(ch[i]>0)s[ch[i]]+=k,fk2[nks2[ch[i]]]+=k;
else s[-ch[i]]-=k,fk2[nks2[-ch[i]]]-=k;
}
}
else
{
for(int i=l;i<=nkf1[k1][1];i++)
{
if(ch[i]>0)s[ch[i]]+=k,fk2[nks2[ch[i]]]+=k;
else s[-ch[i]]-=k,fk2[nks2[-ch[i]]]-=k;
}
for(int i=nkf1[k2][0];i<=r;i++)
{
if(ch[i]>0)s[ch[i]]+=k,fk2[nks2[ch[i]]]+=k;
else s[-ch[i]]-=k,fk2[nks2[-ch[i]]]-=k;
}
for(int i=k1+1;i<k2;i++)fk1[i]+=k;
if(k1+1<k2)for(int i=1;i<=nks2[sz];i++)fk2[i]+=(qz[k2-1][i]-qz[k1][i])*k;
}
}
int main()
{
int n=read();
for(int i=1;i<=n;i++)ls[i]=c[i]=read();
sort(ls+1,ls+1+n);
sz=unique(ls+1,ls+1+n)-ls-1;
for(int i=1;i<=n;i++)c[i]=lower_bound(ls+1,ls+1+sz,c[i])-ls;
for(int i=1;i<=sz;i++)nks2[i]=(i-1)/kc2+1;
for(int i=1;i<=nks2[sz];i++)
{
nkf2[i][0]=nkf2[i-1][1]+1;
nkf2[i][1]=nkf2[i-1][1]+kc2;
}
nkf2[nks2[sz]][1]=sz;
for(int i=1;i<n;i++)
{
int u=read(),v=read();
l[u].push_back(v);
l[v].push_back(u);
}
dfs(1,0);
for(int i=1;i<=cnt;i++)
{
nks1[i]=(i-1)/kc1+1;
if(ch[i]>0)qz[nks1[i]][nks2[ch[i]]]++,al[nks1[i]][ch[i]]++;
else qz[nks1[i]][nks2[-ch[i]]]--,al[nks1[i]][-ch[i]]--;
}
for(int i=1;i<=nks1[cnt];i++)
{
nkf1[i][0]=nkf1[i-1][1]+1;
nkf1[i][1]=nkf1[i-1][1]+kc1;
for(int j=1;j<=nks2[sz];j++)qz[i][j]+=qz[i-1][j];
}
nkf1[nks1[cnt]][1]=cnt;
int m=read();
ll als=0,nw=1;
for(int i=1;i<=m;i++)
{
q[i][0]=read();
if(q[i][0]==1)q[i][1]=read(),q[i][2]=read(),q[i][3]=read();
else if(q[i][0]==3)nw<<=1;
}
for(int i=1;i<=m;i++)
{
if(q[i][0]==1)
{
int x=q[i][1],y=q[i][2];
ll k=q[i][3];
int ql=lca(x,y);
als+=(dis[x]+dis[y]-dis[ql]*2+1)*k;
Add(st[ql],st[x],k*nw);
Add(st[ql]+1,st[y],k*nw);
}
else if(q[i][0]==2)
{
ll qk=(als+1)/2*nw;
for(int k1=1;k1<=nks2[sz];k1++)
{
if(fk2[k1]>=qk)
{
for(int j=nkf2[k1][0];j<=nkf2[k1][1];j++)
{
ll now=s[j];
for(int k2=1;k2<=nks1[cnt];k2++)now+=al[k2][j]*fk1[k2];
if(now>=qk)
{
cout<<ls[j]<<"\n";
break;
}
qk-=now;
}
break;
}
qk-=fk2[k1];
}
}
else
{
als<<=1;
nw>>=1;
}
}
return 0;
}$\mathcal{O}(n\sqrt n)$ 做法
需要两个分块。
首先开一个值域分块维护块内的值出现的次数。具体来说，对于每个块，把树上在块内的点设为 $1$，剩下的是 $0$。每次修改对于一个块的贡献可以用树上前缀和计算，查询的时候枚举块。问题在于，一个点的出现次数怎么算。
注意到，修改操作相当于是单点加，一个点的出现次数就是区间求和，于是再开一个 $\mathcal{O}(\sqrt{n})-\mathcal{O}(1)$ 的分块就做完了。
时间复杂度 $\mathcal{O}(n\sqrt n)$。