[SCOI2015] 情报传递

摘要

有趣的树剖 + 主席树题

奈特公司是一个巨大的情报公司,它有着庞大的情报网络。情报网络中共有 n 名情报员。每名情报员可能有若干名 (可能没有) 下线,除 1 名大头目外其余 n−1 名情报员有且仅有 1 名上线。奈特公司纪律森严,每名情报员只能与自己的上、下线联系,同时,情报网络中任意两名情报员一定能够通过情报网络传递情报。

奈特公司每天会派发以下两种任务中的一个任务:

  1. 搜集情报:指派 T 号情报员搜集情报;
  2. 传递情报:将一条情报从 X 号情报员传递给 Y 号情报员。

情报员最初处于潜伏阶段,他们是相对安全的,我们认为此时所有情报员的危险值为 0;一旦某个情报员开始搜集情报,他的危险值就会持续增加,每天增加 1 点危险值 (开始搜集情报的当天危险值仍为 0,第 2 天危险值为 1,第 3 天危险值为 2,以此类推)。传递情报并不会使情报员的危险值增加。

为了保证传递情报的过程相对安全,每条情报都有一个风险控制值 C。奈特公司认为,参与传递这条情报的所有情报员中,危险值大于 C 的情报员将对该条情报构成威胁。现在,奈特公司希望知道,对于每个传递情报任务,参与传递的情报员有多少个,其中对该条情报构成威胁的情报员有多少个。

即树上动态操作:

  • 修改点权(初始时点权为 INF)
  • 查询路径 上点权在值域 中的点的个数
  • 查询 LCA

我们记录每个情报员开始传递情报的那一天(初始时为 INF),注意到,对于第 天的风险情报员,我们只需要查询点权在 的情报员有多少个即可。所以我们可以直接读入整个询问建立静态主席树,避免了动态修改的过程。

通过建立树上主席树,每个结点继承父结点的版本,然后查询的时候减掉 的部分即可。总复杂度 .

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,root;

struct qxx{int nex,t;};
qxx e[N];
int h[N],cnt;
void add_path(int f,int t){e[++cnt]=(qxx){h[f],t},h[f]=cnt;}

namespace TRD{// 树链剖分
    int par[N],sz[N],dep[N];
    int hvs[N],top[N];
    int szdfs(int u,int p,int deep){dep[u]=deep,sz[u]=1,par[u]=p;
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;// 有向树
            if(v!=p)sz[u]+=szdfs(v,u,deep+1);
        }
        return sz[u];
    }
    void dedfs(int u,int p,int topp){top[u]=topp;
        for(int i=h[u],mxz=0;i;i=e[i].nex){const int &v=e[i].t;
            if(v!=p&&sz[v]>mxz)mxz=sz[v],hvs[u]=v;
        }
        if(!hvs[u])return;
        dedfs(hvs[u],u,topp);
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
            if(v!=p&&v!=hvs[u])dedfs(v,u,v);
        }
    }
    int lca(int x,int y){while(top[x]!=top[y]){if(dep[top[x]]<dep[top[y]])swap(x,y);
            x=par[top[x]];
        }
        return dep[x]<dep[y]?x:y;
    }
}
int q;
namespace CMT{// 主席树 
    const int CMT_SZ=18*(1<<18);
    int val[N],tot;
    int rt[CMT_SZ],lc[CMT_SZ],rc[CMT_SZ],cnt[CMT_SZ];//cnt: 当前值域区间内数的个数
    int build(int l,int r){// 建立版本 0
        int u=++tot,mid=(l+r)>>1;
        if(l<r)lc[u]=build(l,mid),rc[u]=build(mid+1,r);
        return u;
    }
    int modify(int u,int v,int l=1,int r=q+1){// 从旧版本中的 u 结点修改得来
        int u2=++tot,mid=(l+r)>>1;
        if(l==r)return cnt[u2]=cnt[u]+1,u2;
        if(v<=mid)lc[u2]=modify(lc[u],v,l,mid),rc[u2]=rc[u];
        else lc[u2]=lc[u],rc[u2]=modify(rc[u],v,mid+1,r);
        return cnt[u2]=cnt[u]+1,u2;
    }
    void dfsbuild(int u,int p){//u 从 p 继承而来
        rt[u]=modify(rt[p],val[u]);
        for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
            if(v!=p)dfsbuild(v,u);
        }
    }
    int query(int u,int L,int R,int l=1,int r=q+1){// 查询值域 [L,R] 内的数的个数
        if((L<=l&&r<=R)||!cnt[u])return cnt[u];
        int mid=(l+r)>>1,res=0;
        if(L<=mid)res+=query(lc[u],L,R,l,mid);
        if(mid<R)res+=query(rc[u],L,R,mid+1,r);
        return res;
    }
    int qnode(int x,int L,int R){return query(rt[x],L,R);
    }
}
int x[N],y[N],c[N],t[N],k[N];
int main(){scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int p;
        scanf("%d",&p);
        if(p==0)root=i;
        else add_path(p,i);
    }
    TRD::szdfs(root,0,1);
    TRD::dedfs(root,root,root);
    scanf("%d",&q);
    for(int i=1;i<=n;i++)CMT::val[i]=q+1;// 初始化为最大值
    for(int i=1;i<=q;i++){scanf("%d",&k[i]);
        if(k[i]==1)scanf("%d%d%d",&x[i],&y[i],&c[i]);
        else scanf("%d",&t[i]),CMT::val[t[i]]=i;// 情报员 t[i] 在第 i 天开始收集情报
    }
    CMT::rt[0]=CMT::build(1,q+1);
    CMT::dfsbuild(root,0);// 从 0 继承
    // 开始处理询问
    for(int i=1;i<=q;i++){if(k[i]!=1)continue;
        int z=TRD::lca(x[i],y[i]);
        int a=CMT::qnode(x[i],0,i-c[i]-1)+CMT::qnode(y[i],0,i-c[i]-1)
            -CMT::qnode(z,0,i-c[i]-1)-CMT::qnode(TRD::par[z],0,i-c[i]-1);
        int b=TRD::dep[x[i]]+TRD::dep[y[i]]
            -TRD::dep[z]-TRD::dep[TRD::par[z]];
        printf("%d %d\n",b,a);
    }
    return 0;
}
/*
 * 先读取所有询问建立静态主席树;
 * 第 i 天危险值为 C,即查询 i-c<x<i 的值的个数,那么两次查询两边即可;
 * 初始化每个人的权值为 INF;
 * 写一个树剖来求 LCA;
 * BUG#1: qnode 在主函数里调用的时候,参数给错
 * BUG#2: CMT 内存没开够
 */

  转载请注明: Sshwy's Blog [SCOI2015] 情报传递

 上一篇
[POI2006]OKR-Periods of Words [POI2006]OKR-Periods of Words
摘要 题意:求一个串所有前缀的最长周期之和。这里的周期是非严格周期,不能为自身 即求最短 border,那么 就是最长周期。注意到 数组求的是最长 ,而
2019.04.10
下一篇 
[LuoguP1251] 餐巾计划问题 [LuoguP1251] 餐巾计划问题
摘要 复习一下网络流 一个餐厅在相继的 天里,每天需用一些餐巾。第 天需要 块餐巾 。餐厅可以购买新的餐巾, 每块餐巾的费用为 ;或者把旧餐巾送到快洗部,洗一块需
2019.04.06
  目录