UESTC 574 High-level ancients-白红宇

UESTC 574 High-level ancients

阅读量：6819 次

发布时间：2019-06-26

本文共 2890 字，大约阅读时间需要 9 分钟。

分析：

无论父节点增加了多少，子节点的增量总比父节点多1。

这种差分的关系是保存不变的，我们可以一遍dfs根据结点深度得到在根结点的每个点的系数。

估且把一开始的结点深度称做c0吧，对于子树的修改就只是结点的系数就只是c0+d，d是修正值。

dfs得到树的dfs序列，子树的结点连续，就变成区间更新了。

区间更新的时候，在线段树上保存好初始的系数，修改的时候把系数的lazy标记和普通的lazy标记分开。

这道题学到的新东西：在线段树上不仅可以总体+d，还可以总体增加某一系列特定的系数。

这个系数甚至是可变的，感觉这里可以挖掘一下。

/**********************************************************            ------------------                          **   author AbyssFish                                     ***********************************************************/#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;typedef long long ll;const int MAX_N = 5e4+5;//MAX_P = 1e5 , K <= 1e3int fa[MAX_N];int son[MAX_N], bro[MAX_N];int N;int dep[MAX_N];int L[MAX_N], R[MAX_N];int c[MAX_N]; //dfs_orderint dfs_clk;void dfs(int u = 1,int d = 1){ c[dfs_clk] = dep[u] = d; L[u] = dfs_clk++; for(int v = son[u]; v; v = bro[v]){ dfs(v,d+1); } R[u] = dfs_clk;}#define para int o = 1,int l = 0,int r = N#define lo (o<<1)#define ro (o<<1|1)#define Tvar int md = (l+r)>>1;#define lsn lo,l,md#define rsn ro,md,r#define insd ql <= l && r <= qrconst int ST_SIZE = 1<<17;ll t_c[ST_SIZE];//O 5e4*5e4/2ll sum[ST_SIZE];//O 1e5*(1e3*5e4+5e4*5e4/2)int dwn_c[ST_SIZE];//O 1e5ll dwn[ST_SIZE];//O (5e4+1e3)*1e5void build(para){ sum[o] = 0; if(r-l == 1){ t_c[o] = c[l]; } else { dwn_c[o] = dwn[o] = 0; Tvar build(lsn); build(rsn); t_c[o] = t_c[lo]+t_c[ro]; }}inline void sink_d(int o,ll d,int len){ sum[o] += len*d; dwn[o] += d;}inline void sink_c(int o,int k){ sum[o] += t_c[o]*k; dwn_c[o] += k;}inline void push_down(int o,int l,int r){ if(dwn_c[o]){ sink_c(lo,dwn_c[o]); sink_c(ro,dwn_c[o]); dwn_c[o] = 0; } if(dwn[o]){ Tvar sink_d(lo,dwn[o],md-l); sink_d(ro,dwn[o],r-md); dwn[o] = 0; }}#define upara d,ql,qrvoid update(int d,int ql,int qr,para){ if(insd){ sink_d(o,d,r-l);//O 5e4+1e3 sink_c(o,1); } else { Tvar push_down(o,l,r); if(ql < md) update(upara,lsn); if(qr > md) update(upara,rsn); sum[o] = sum[lo] + sum[ro]; }}ll query(int ql,int qr,para){ if(insd) return sum[o]; else { Tvar push_down(o,l,r); ll re = 0; if(ql < md) re += query(ql,qr,lsn); if(qr > md) re += query(ql,qr,rsn); return re; }}void solve(){ int i, P; scanf("%d%d",&N,&P); memset(son+1,0,sizeof(int)*N); for(i = 2; i <= N; i++){ scanf("%d",fa+i); bro[i] = son[fa[i]]; son[fa[i]] = i; } dfs_clk = 0; dfs(); build(); char op[2]; int u; while(P--){ scanf("%s%d",op,&u); if(*op == 'A'){ scanf("%d",&i); update(i-dep[u],L[u],R[u]); } else { printf("%lld\n",query(L[u],R[u])); } }}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int T, kas = 0; scanf("%d",&T); while(++kas <= T){ printf("Case #%d:\n",kas); solve(); } return 0;}