UOJ 284. 快乐游戏鸡

倒着做。用lct维护

我们把每个询问转化为总和减去大于等于最大权值的部分的后缀和。

接着我们按w从大到小加入点，考虑维护每个点的子树中的最小深度。

这个怎么维护呢，考虑一个点肯定是更新它到根的路径，所以我们用类似LCT的access的方法更新，我们可以保证随时每个链的最小深度都相同，如果当前的链的最小深度小于用来更新的值就直接退出，否则的话我们就更新，最后再把这些更新了的链连起来。

复杂度显然是

答案也很好算，记录一个后缀和即可，你会发现更新的时候也很好打标记，询问也很好处理。

#include<bits/stdc++.h>
#define Max(a,b) (a>b?a:b)
#define nrt(x) (ch[fa[x]][0]==x||ch[fa[x]][1]==x)
#define N 500007
#define SI 23
#define LL long long
int Val[N],oo,val[N],fa[N],ch[N][2],dep[N],w[N],ma[N][SI],pos1[N],j;
LL lazy[N],sum[N],ans[N];
using namespace std;
void write(LL x){if (x<10) {putchar('0'+x); return;} write(x/10); putchar('0'+x%10);}
inline void writeln(LL x){ if (x<0) putchar('-'),x*=-1; write(x); putchar('
'); }
inline void writel(LL x){ if (x<0) putchar('-'),x*=-1; write(x); putchar(' '); }
template <class T>
inline void read(T& x){
    static char c; static int b;
    for (c=getchar(),b=1;!isdigit(c);c=getchar()) if (c=='-') b=-1;
    for (x=0;isdigit(c);c=getchar()) x=x*10+c-48;
    x*=b;
}
void rotate(int x) {
    int y=fa[x],z=fa[y],l,r;
    l=(ch[y][1]==x); r=l^1;
    if (nrt(y)) ch[z][ch[z][1]==y]=x;
    fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;
    ch[y][l]=ch[x][r]; ch[x][r]=y;
}
void pushdown(int x){
    if (nrt(x)) pushdown(fa[x]);
    if (lazy[x]) {
        lazy[ch[x][0]]+=lazy[x]; lazy[ch[x][1]]+=lazy[x];
        sum[ch[x][0]]+=lazy[x]; sum[ch[x][1]]+=lazy[x];
        Val[ch[x][0]]=Val[x]; Val[ch[x][1]]=Val[x];
        lazy[x]=0;
    }
}
void splay(int x){
    pushdown(x);
    for (;nrt(x);) {
        int y=fa[x],z=fa[y];
        if (nrt(y)) 
         if (ch[y][1]==x^ch[z][1]==y) rotate(x); else rotate(y);
        rotate(x);
    }
}
//void access(int x){
//    for (int t=0;x;t=x,x=fa[x]) splay(x),ch[x][1]=t;
//}
int t,p[N],need[N],n,q,qu,que,f[N][SI],pos2[N];
void add(int y){
    if (!(f[y][0])) return; 
    for (int t=0,x=f[y][0];x;t=x,x=fa[x]) {
        splay(x);
        if (Val[x]<=dep[y]) break;
        lazy[x]+=(1ll*(dep[y]-(Val[x]==oo?0:Val[x]))*w[y]);
        sum[x]+=(1ll*(dep[y]-(Val[x]==oo?0:Val[x]))*w[y]);
        Val[x]=dep[y];
        ch[x][1]=0;
        if (lazy[x]) {
           lazy[ch[x][0]]+=lazy[x]; lazy[ch[x][1]]+=lazy[x];
           sum[ch[x][0]]+=lazy[x]; sum[ch[x][1]]+=lazy[x];
           Val[ch[x][0]]=Val[x]; Val[ch[x][1]]=Val[x];
           lazy[x]=0;
        }
        ch[x][1]=t; 
    }
    splay(f[y][0]);
}
inline LL query(int x,int y){
    splay(x);
    return sum[x]-(LL)(Val[x]==oo?0:Val[x])*y; 
}
signed main() {
    memset(Val,126,(sizeof Val)); oo=Val[0];
    read(n);
    for (int i=1;i<=n;i++) read(w[i]),ma[i][0]=w[i],pos1[i]=i; dep[1]=1;
    for (int i=2;i<=n;i++) {
      read(fa[i]),dep[i]=dep[fa[i]]+1; 
      f[i][0]=fa[i]; 
      for (int j=1;j<SI;j++) ma[i][j]=Max(ma[i][j-1],ma[f[i][j-1]][j-1]),f[i][j]=f[f[i][j-1]][j-1];
    }
    read(q);
    for (int i=1;i<=q;i++) {
      read(qu),read(que); 
      ans[i]=dep[que]-dep[qu]; pos2[i]=i;
      if (ans[i]<=1) continue;
      need[i]=1;
      p[i]=qu;
      val[i]=0; t=fa[que];
      for (int j=SI-1;~j;j--) 
        if (dep[f[t][j]]>=dep[qu]) 
         val[i]=Max(val[i],ma[t][j]),t=f[t][j];
    }
    for (int i=1;i<=n;i++) dep[i]--;
    sort(pos1+1,pos1+n+1,[&](int _x,int _y){return w[_x]>w[_y];});
    sort(pos2+1,pos2+q+1,[&](int _x,int _y){return val[_x]>val[_y];});
    for (int i=1;i<=q;i++)  if (need[pos2[i]]) {
        while (j<n&&w[pos1[j+1]]>val[pos2[i]])  
           add(pos1[++j]);
        ans[pos2[i]]-=query(p[pos2[i]],val[pos2[i]]);
    }
    while (j<n) add(pos1[++j]);
    for (int i=1;i<=q;i++) if (need[i]) ans[i]+=query(p[i],0)-(LL)val[i]*dep[p[i]];
    for (int i=1;i<=q;i++) writeln(ans[i]);
    return 0;
}

相关推荐