都成老年选手了，能记点就记点吧。
9.10
BZOJ3786 星际探索
不知道为啥瞥见了这题题解，所以成了个玛丽题，跑出括号序后成区间问题，平衡树维护区间移动，加法。
对于移动一段区间，平衡树需要维护节点内正的贡献数量，方便区间加法，然后区间移动的变化量要算清。
点击查看代码
#include<bits/stdc++.h>
#define int long long
typedef long long ll;
typedef unsigned long long ull;
inline int read(){char ch=getchar();int x=0,f=1;for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);return x*f;}
const int N=2e5+10;
std::mt19937 myrand(1);
int n,m,dfc,dfnl[N],dfnr[N],v[N];
std::vector<int> e[N];
inline void dfs(int u,int fa){
dfnl[u]=++dfc;
for(int v:e[u])if(v!=fa)dfs(v,u);
dfnr[u]=++dfc;
}
struct FHQ{
int root,x,y,cnt,size[N],ls[N],rs[N],sum[N],val[N],w[N],pd[N],tagp[N],tagd[N],rnd[N],num[N],fa[N];
inline int new_node(int k,int W,int P){val[++cnt]=k,w[cnt]=sum[cnt]=W,num[cnt]=pd[cnt]=P,size[cnt]=1,rnd[cnt]=myrand();return cnt;}
inline void update(int p){fa[ls[p]]=p,fa[rs[p]]=p; size[p]=size[ls[p]]+rs[p]+1;sum[p]=sum[ls[p]]+sum[rs[p]]+w[p];num[p]=num[ls[p]]+num[rs[p]]+pd[p];}
inline void pushdown(int p){
fa[ls[p]]=p,fa[rs[p]]=p;
if(tagp[p]){tagp[ls[p]]+=tagp[p],tagp[rs[p]]+=tagp[p],val[ls[p]]+=tagp[p],val[rs[p]]+=tagp[p];}
if(tagd[p]){tagd[ls[p]]+=tagd[p],tagd[rs[p]]+=tagd[p],sum[ls[p]]+=num[ls[p]]*tagd[p],sum[rs[p]]+=num[rs[p]]*tagd[p];w[ls[p]]+=pd[ls[p]]*tagd[p],w[rs[p]]+=pd[rs[p]]*tagd[p];}
return tagd[p]=tagp[p]=0,void();
}
inline void split(int fx,int fy,int p,int k,int &x,int &y){
if(!p){return x=y=0,void();}
pushdown(p);
if(val[p]<=k)x=p,fa[x]=fx,fx=fx,split(fx,fy,rs[p],k,rs[p],y);
else y=p,fa[y]=fy,fy=y,split(fx,fy,ls[p],k,x,ls[p]);
update(p);
}
inline int merge(int u,int v){
if(!u||!v){return u|v;}
if(rnd[u]<rnd[v]){pushdown(u);rs[u]=merge(rs[u],v);fa[rs[u]]=u,update(u);return u;}
else{pushdown(v);ls[v]=merge(u,ls[v]);fa[ls[v]]=v;update(v);return v;}
}
inline void F(int x){if(!x)return;F(fa[x]);pushdown(x);}
inline int find(int u){F(fa[u]);return val[u];}
inline void insert(int k,int W,int P){split(0,0,root,k,x,y);root=merge(merge(x,new_node(k,W,P)),y);fa[root]=0;}
inline void move(int u,int f){
int l=find(2*u-1),r=find(2*u),pos=find(2*f-1),z=0;
int len=r-l+1,d;
if(l>pos){
d=pos+1-l;
split(0,0,root,r,x,y);split(0,0,x,l-1,x,z);
tagp[z]+=d,val[z]+=d;
int c=0;split(0,0,x,pos,x,c);
tagp[c]+=len,val[c]+=len;
root=merge(merge(merge(x,z),c),y);
}else{
d=pos-r;
split(0,0,root,r,x,y);split(0,0,x,l-1,x,z);
tagp[z]+=d,val[z]+=d;
int c=0;split(0,0,y,pos,c,y);
tagp[c]-=len,val[c]-=len;
root=merge(merge(merge(x,c),z),y);
}fa[root]=0;
}
inline void add(int u,int d){
int l=find(2*u-1),r=find(2*u);
int z;split(0,0,root,r,x,y);split(0,0,x,l-1,x,z);
sum[z]+=num[z]*d,w[z]+=pd[z]*d,tagd[z]+=d;
root=merge(merge(x,z),y);fa[root]=0;
}
inline int ask(int u){
int l=find(2*u-1);
split(0,0,root,l,x,y);int res=sum[x];
root=merge(x,y);fa[root]=0;
return res;
}
}s;
signed main(){
// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);
n=read();for(int i=2;i<=n;++i){int x=read();e[x].emplace_back(i);e[i].emplace_back(x);}
for(int i=1;i<=n;++i){v[i]=read();}
dfs(1,0);
for(int i=1;i<=n;++i)s.insert(dfnl[i],v[i],1),s.insert(dfnr[i],-v[i],-1);
m=read();
for(int i=1;i<=m;++i){
char ch=getchar();while(ch<'A'||ch>'Z')ch=getchar();
if(ch=='Q')std::cout<<s.ask(read())<<'\n';
if(ch=='C'){int u=read(),fa=read();s.move(u,fa);}
if(ch=='F'){int u=read(),d=read();s.add(u,d);}
}
}