题目描述
传送门
题目大意：n个点的一棵树，有m个骑士，每个骑士居住在n个点中的一个，有一个武力值fi，有三种操作： 1 x y 询问居住在树链x-y上前k大的骑士的武力值 2 x y 编号为x的骑士居住地改为y 3 x y 编号为x的骑士武力值改为y
题解
k比较小 树链剖分，对线段树中的底层节点维护一个multiset，维护所有居住在这个点的骑士的武力值，然后线段树中的每一个点开一个结构体，表示这段区间内武力值前k大的骑士的武力值，然后update的时候归并一下就行了。
代码
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define N 40005
int n,m,q,k,dfs_clock;
int F[N],P[N];
int tot,point[N],nxt[N<<
1],v[N<<
1];
int father[N],son[N],size[N],h[N],top[N],num[N];
struct data{
int cnt,val[
25];}tr[N<<
2];
multiset <int> leaf[N];
void add(
int x,
int y){++tot;nxt[tot]=point[x];point[x]=tot;v[tot]=y;}
void dfs_1(
int x,
int fa)
{
size[x]=
1;father[x]=fa;h[x]=h[fa]+
1;
for (
int i=point[x];i;i=nxt[i])
if (v[i]!=fa)
{
dfs_1(v[i],x);
size[x]+=size[v[i]];
if (size[v[i]]>size[son[x]]) son[x]=v[i];
}
}
void dfs_2(
int x,
int fa)
{
if (x==son[fa]) top[x]=top[fa];
else top[x]=x;
num[x]=++dfs_clock;
if (son[x]) dfs_2(son[x],x);
for (
int i=point[x];i;i=nxt[i])
if (v[i]!=fa&&v[i]!=son[x])
dfs_2(v[i],x);
}
data merge(data a,data b)
{
int now=
0,l=
1,r=
1;
data ans;ans.cnt=
0;
while (l<=a.cnt&&r<=b.cnt&&now<k)
{
if (a.val[l]>=b.val[r]) ans.val[++now]=a.val[l++];
else ans.val[++now]=b.val[r++];
}
while (l<=a.cnt&&now<k) ans.val[++now]=a.val[l++];
while (r<=b.cnt&&now<k) ans.val[++now]=b.val[r++];
ans.cnt=now;
return ans;
}
void change(
int now,
int l,
int r,
int x,
int y,
int opt)
{
int mid=(l+r)>>
1;
if (l==r)
{
multiset<int>::iterator t;
if (opt==
1)
leaf[l].insert(y);
else
{
t=leaf[l].find(y);
leaf[l].erase(t);
}
int cnt=
0;
if (!leaf[l].empty())
{
t=leaf[l].end();--t;
while (cnt<=k)
{
tr[now].val[++cnt]=*t;
if (t==leaf[l].begin())
break;
--t;
}
}
tr[now].cnt=cnt;
return;
}
if (x<=mid) change(now<<
1,l,mid,x,y,opt);
else change(now<<
1|
1,mid+
1,r,x,y,opt);
tr[now]=merge(tr[now<<
1],tr[now<<
1|
1]);
}
data query(
int now,
int l,
int r,
int lr,
int rr)
{
int mid=(l+r)>>
1;
data ans;ans.cnt=
0;
if (lr<=l&&r<=rr)
return tr[now];
if (lr<=mid) ans=merge(ans,query(now<<
1,l,mid,lr,rr));
if (mid+
1<=rr) ans=merge(ans,query(now<<
1|
1,mid+
1,r,lr,rr));
return ans;
}
data QUERY(
int s,
int t)
{
int f1=top[s],f2=top[t];
data ans;ans.cnt=
0;
while (f1!=f2)
{
if (h[f1]<h[f2])
{
swap(f1,f2);
swap(s,t);
}
ans=merge(ans,query(
1,
1,n,num[f1],num[s]));
s=father[f1];
f1=top[s];
}
if (num[s]>num[t]) swap(s,t);
ans=merge(ans,query(
1,
1,n,num[s],num[t]));
return ans;
}
int main()
{
scanf(
"%d",&n);
for (
int i=
1;i<n;++i)
{
int x,y;
scanf(
"%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs_1(
1,
0);
dfs_2(
1,
0);
scanf(
"%d",&m);
for (
int i=
1;i<=m;++i)
scanf(
"%d%d",&F[i],&P[i]);
scanf(
"%d%d",&q,&k);
for (
int i=
1;i<=m;++i)
change(
1,
1,n,num[P[i]],F[i],
1);
while (q--)
{
int opt,x,y;
scanf(
"%d%d%d",&opt,&x,&y);
if (opt==
1)
{
data ans=QUERY(x,y);
if (!ans.cnt)
puts(
"-1");
else
{
for (
int i=
1;i<=ans.cnt;++i)
printf(
"%d ",ans.val[i]);
puts(
"");
}
}
else if (opt==
2)
{
change(
1,
1,n,num[P[x]],F[x],-
1);
P[x]=y;
change(
1,
1,n,num[P[x]],F[x],
1);
}
else
{
change(
1,
1,n,num[P[x]],F[x],-
1);
F[x]=y;
change(
1,
1,n,num[P[x]],F[x],
1);
}
}
}
