Loading...

洛谷P2633 count on a tree

check评论:0 条 remove_red_eye浏览量:868 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2018-09-30

qwq,这道题查询树上第$k$小,一看就知道是主席树+树上差分啦

所以就这么搞出来了qwq,我们拿树剖来建主席树,顺便就求$lca$,然后$[u,v]$差分就是$sum[l[u]]+sum[l[v]]-sum[l[lca(u,v)]]-sum[l[f[lca(u,v)]]]$

code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
int sum[maxn<<5],l[maxn<<5],r[maxn<<5],t[maxn],head[maxn],b[maxn],m;
int fa[maxn],son[maxn],dep[maxn],seg[maxn],siz[maxn],top[maxn],in[maxn],out[maxn]; 
int cnt,n,q,tot,xx,rk[maxn];
struct node
{
    int num,v;
}a[maxn];
struct edge
{
    int next,to;
}e[maxn<<1];
bool cmp(node x,node y)
{
    return x.v<y.v;
}
void add(int u,int v)
{
    cnt++;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void update(int &u,int pre,int lf,int rg,int k)
{
    u=++cnt;
    sum[u]=sum[pre]+1;
    l[u]=l[pre];
    r[u]=r[pre];
    if(lf<rg)
    {
        int mid=(lf+rg)>>1;
        if(k<=mid) 
        {
            update(l[u],l[pre],lf,mid,k);
        }
        else 
        {
            update(r[u],r[pre],mid+1,rg,k);
        }
    }
}
void dfs1(int u,int f)
{
    update(t[u],t[f],1,n,b[u]);
    siz[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u])
        {
            continue;
        }
        dep[v]=dep[u]+1;
        fa[v]=u;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])
        {
            son[u]=v;
        }
    }
}
void dfs2(int u,int tp)
{
    cnt++;
    in[u]=cnt;
    top[u]=tp;
    if(son[u])
    {
        dfs2(son[u],tp);
    }
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa[u]||v==son[u])
        {
            continue;
        }
        dfs2(v,v);
    }
}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])
        {
            swap(u,v);
        }
        u=fa[top[u]];
    } 
    if(dep[u]>dep[v])
    {
        swap(u,v);
    }
    return u;
}
int query(int a,int b,int c,int d,int lf,int rg,int k)
{
    if(lf==rg)
    {
        return lf;
    }
    int sums=sum[l[a]]+sum[l[b]]-sum[l[c]]-sum[l[d]];
    int mid=(lf+rg)>>1;
    if(sums>=k)
    {
        return query(l[a],l[b],l[c],l[d],lf,mid,k);
    }
    else
    {
        return query(r[a],r[b],r[c],r[d],mid+1,rg,k-sums);
    }
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i].v);
        b[i]=a[i].v;
        a[i].num=i;
    }
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    sort(a+1,a+n+1,cmp);
    a[0].v=-1;
    for(int i=1;i<=n;i++)
    {
        if(a[i].v!=a[i-1].v) 
        {
            rk[++xx]=b[a[i].num];
            b[a[i].num]=xx;
        }
        else 
        {
            b[a[i].num]=xx;
        } 
    }
    int lastans=0;
    cnt=0;
    dep[0]=1;
    dfs1(1,0);
    cnt=0;
    dfs2(1,1);
    for(int i=1;i<=q;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        x^=lastans;
        int k=lca(x,y);
        int tql=query(t[x],t[y],t[k],t[fa[k]],1,n,z);
        printf("%d\n",rk[tql]);
        lastans=rk[tql];
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名