洛谷 4216 BZOJ 4448 [SCOI2015]情报传递

【题解】

　　每个情报员的危险值val[i]应该是一个分段函数，前面一段是平行于x轴的横线，后面一段是一次函数。我们可以用fx(t)=t-b[x]表示这个一次函数。每次询问一条链上fx(t)大于c的点的个数，也就是问有多少个点满足t-b[x]>c，移项得b[x]<t-c，不等式左边只与点有关，可以当做点权，右边只与询问有关。因此我们可以写没有修改的主席树。

　　同时这道题也可以离线后用树状数组写。我们维护某个点到根的链上小于等于某个值的数的个数Cnt，这开一个权值树状数组就可以做到。这样每个询问(x,y)的答案就是Cnt[x]+Cnt[y]-Cnt[lca]-Cnt[fa[lca]]. 我们dfs进行维护，进入这个点的时候在树状数组中加入点权，退出这个点的时候删除点权，同时在每个点计算与这个点有关的答案即可。

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #define N 200010

 #define rg register

 using namespace std;

 int n,m,rt,tot,cnt,ret,last[N],ans[N],ans2[N],fa[N],hvy[N],size[N],top[N],dep[N],t[N],val[N];

 vector<int>son[N];

 struct rec{

     int pos,val,type,pre;

 }data[N<<];

 inline int read(){

     int k=,f=; char c=getchar();

     while(c<''||c>'')c=getchar();

     while(''<=c&&c<='')k=k*+c-'',c=getchar();

     return k*f;

 }

 void dfs1(int x){

     size[x]=; dep[x]=dep[fa[x]]+;

     for(rg int i=,s;i<son[x].size();i++){

         dfs1(s=son[x][i]); size[x]+=size[s];

         if(size[s]>size[hvy[x]]) hvy[x]=s;

     }

 }

 void dfs2(int x,int tp){

     top[x]=tp;

     if(hvy[x]) dfs2(hvy[x],tp);

     for(rg int i=,s;i<son[x].size();i++)

         if((s=son[x][i])!=hvy[x]) dfs2(s,s);

 }

 inline int lca(int x,int y){

     int f1=top[x],f2=top[y];

     while(f1!=f2){

         if(dep[f1]<dep[f2]) swap(x,y),swap(f1,f2);

         x=fa[f1]; f1=top[x];

     }

     return dep[x]<dep[y]?x:y;

 }

 void dfs(int x){

     for(rg int i=val[x];i<=m;i+=(i&-i)) t[i]++;

     for(rg int i=last[x];i;i=data[i].pre){

         ret=;

         for(rg int j=data[i].val-;j>;j-=(j&-j)) ret+=t[j];

         ans[data[i].pos]+=data[i].type*ret;

     }

     for(rg int i=;i<son[x].size();i++) dfs(son[x][i]);

     for(rg int i=val[x];i<=m;i+=(i&-i)) t[i]--;

 }

 int main(){

     n=read();

     for(rg int i=;i<=n;i++){

         fa[i]=read();

         if(!fa[i]) rt=i;

         son[fa[i]].push_back(i);

     }

     m=read();

     for(rg int i=;i<=n;i++) val[i]=m;

     dfs1(rt); dfs2(rt,rt);

     for(rg int t=;t<=m;t++){

         int opt=read();

         if(opt==){

             int x=read(),y=read(),c=read(),Lca=lca(x,y);

             data[++tot]=(rec){++cnt,t-c,,last[x]}; last[x]=tot;

             data[++tot]=(rec){cnt,t-c,,last[y]}; last[y]=tot;

             data[++tot]=(rec){cnt,t-c,-,last[Lca]}; last[Lca]=tot;

             data[++tot]=(rec){cnt,t-c,-,last[fa[Lca]]}; last[fa[Lca]]=tot;

             ans2[cnt]=dep[x]+dep[y]-*dep[Lca]+;

         }

         else{

             int x=read(); if(val[x]==m) val[x]=t;

         }

     }

     dfs(rt);

     for(rg int i=;i<=cnt;i++) printf("%d %d\n",ans2[i],ans[i]);

     return ;

 }

巴特西

洛谷 4216 BZOJ 4448 [SCOI2015]情报传递

最新文章

热门文章