BruceJay's Blog

BZOJ1146 网络管理Network

| Comments

To start with

带修改的树上路径第k大

Problem

Solution

Bruce模仿区间第k大的做法,树状数组套主席树。
用Dfs序将树的问题转化为区间问题。
关于点x的权值线段树ax维护x到根各个权值出现的次数。
对于这一题,修改我们需要修改Dfs序上连续的一些点的权值线段树,而询问只需要询问一个点的权值线段树。所以用差分的方法结合树状数组来维护这个权值线段树。
修改时修改该点所在的子树在Dfs序中代表的区间。询问(u,v)时,假设lca(u,v)=x,fa[x]=y,询问的就是权值线段树au+av-ax-ay。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 100100;
const int Size = 30001000;
struct node{int k,x,y,lca;}q[N];
struct Edge{int v,nxt;}e[N<<1];
int a[N]; int c[N<<1];
int Start[N]; int End[N];
int dep[N]; int Log[N]; int root[N];
int head[N]; int f[19][N];
int tr[Size][2]; int sum[Size];
int g[2][N]; int num[2];
int Time_block=0;
int n,m,cnt=0,sz=0,edges=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v)
{
    e[++edges].v=v;
    e[edges].nxt=head[u];
    head[u]=edges;
}

int Find(int x)
{
    int l=1,r=cnt,ans=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(x>=c[mid]) l=mid+1,ans=mid;
        else r=mid-1;
    }
    return ans;
}

void Dfs(int u,int d,int p)
{
    Start[u]=++Time_block;
    f[0][u]=p; dep[u]=d;
    for(int i=1;i<=Log[d];i++)
        f[i][u]=f[i-1][f[i-1][u]];
    for(int i=head[u];i;i=e[i].nxt)
        if(e[i].v!=p) Dfs(e[i].v,d+1,u);
    End[u]=Time_block;
}

int Lca(int u,int v)
{
    if(dep[u]>dep[v]) swap(u,v);
    int t=dep[v]-dep[u];
    for(int i=0;i<=18;i++)  
        if((t>>i)&1) v=f[i][v];
    if(u==v) return u;
    for(int i=18;i>=0;i--)
        if(f[i][u]!=f[i][v])
            u=f[i][u],v=f[i][v];
    return f[0][u];
}

void Update(int last,int l,int r,int &t,int pos,int v)
{
    if(!t) t=++sz; sum[t]=sum[last]+v;
    tr[t][0]=tr[last][0]; tr[t][1]=tr[last][1];
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) Update(tr[last][0],l,mid,tr[t][0],pos,v);
    else Update(tr[last][1],mid+1,r,tr[t][1],pos,v);
}

void Modify(int x,int pos,int v)
{
    for(int i=x;i<=n;i+=(i&-i))
        Update(root[i],1,cnt,root[i],pos,v);
}

int Query(int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1,t=0;
    for(int i=1;i<=num[1];i++) t+=sum[tr[g[1][i]][1]];
    for(int i=1;i<=num[0];i++) t-=sum[tr[g[0][i]][1]];
    if(t>=k){
        for(int i=1;i<=num[1];i++) g[1][i]=tr[g[1][i]][1];
        for(int i=1;i<=num[0];i++) g[0][i]=tr[g[0][i]][1];
        return Query(mid+1,r,k);
    }
    else{
        for(int i=1;i<=num[1];i++) g[1][i]=tr[g[1][i]][0];
        for(int i=1;i<=num[0];i++) g[0][i]=tr[g[0][i]][0];
        return Query(l,mid,k-t);
    }
}

void Get(int x,int t)
{
    for(int i=x;i;i-=(i&-i))
        g[t][++num[t]]=root[i];
}

int main()
{
    int u,v;
    freopen("1146.in","r",stdin);
    freopen("1146.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) c[++cnt]=a[i];
    Log[0]=-1; for(int i=1;i<=n;i++) Log[i]=Log[i>>1]+1;
    for(int i=1;i<n;i++){
        u=read(); v=read();
        Addedge(u,v); Addedge(v,u);
    }
    Dfs(1,1,0);
    for(int i=1;i<=m;i++){
        q[i].k=read(); q[i].x=read(); q[i].y=read();
        if(!q[i].k) c[++cnt]=q[i].y;
        else q[i].lca=Lca(q[i].x,q[i].y);
    }
    sort(c+1,c+cnt+1); int tot=1;
    for(int i=2;i<=cnt;i++) if(c[i]!=c[tot]) c[++tot]=c[i];
    cnt=tot;
    for(int i=1;i<=n;i++){
        int pos=Find(a[i]);
        Modify(Start[i],pos,1);
        Modify(End[i]+1,pos,-1);
        if(m<0) printf("%d\n",i);
    }
    for(int i=1;i<=m;i++){
        if(q[i].k){
            num[0]=num[1]=0; tot=0;
            Get(Start[q[i].x],1); tot+=dep[q[i].x];
            Get(Start[q[i].y],1); tot+=dep[q[i].y];
            Get(Start[q[i].lca],0); tot-=dep[q[i].lca];
            Get(Start[f[0][q[i].lca]],0); tot-=dep[f[0][q[i].lca]];
            if(tot<q[i].k) puts("invalid request!");
            else printf("%d\n",c[Query(1,cnt,q[i].k)]);
        }
        else{
            int pos=Find(a[q[i].x]);
            Modify(Start[q[i].x],pos,-1);
            Modify(End[q[i].x]+1,pos,1);
            a[q[i].x]=q[i].y;
            pos=Find(a[q[i].x]);
            Modify(Start[q[i].x],pos,1);
            Modify(End[q[i].x]+1,pos,-1);
        }
    }
    return 0;
}}

Last but not least

这题空间是个大坑啊,Bruce被这个坑了很久。

Comments

comments powered by Disqus