[BZOJ4336][BJOI2015]骑士的旅行（树链剖分+线段树+multiset+归并）

题目描述

题目大意：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);
        }
    }
}