LNOI2016 LCA
好题啊qaq
就是主席树的区间修改啊
蛤？不会主席树区间修改？我也不会qaq
好像不太容易进行pushdown操作
但是有一个好东西叫做标记永久化啊！
于是学习一波姿势 ：
https://www.cnblogs.com/Hallmeow/p/8004676.html
https://www.cnblogs.com/wozaixuexi/p/9462461.html
假设每个节点维护一个sum和add
核心思想就是修改的时候沿途修改经过的节点的sum
当修改区间与当前区间完全重合时更新add标记
查询的时候沿途累加add标记，返回sum+add*len的和
求(u,v)的 LCA 的一个技巧是将u到根节点的路径打上标记，查询v到根节点的和，显然树剖+线段树嘛（当然更可以LCT啦）
这题其实可以询问离线，把（l,r) 的询问拆成 (1,l-1) 和 (1,r) ，这样可以按时间顺序向线段树中插入节点
但这题还有一个加强版：HNOI2015开店 强制在线
那怎么办啊qaq
主席树嘛，区间修改的主席树嘛，于是这道题我也是这么写的
#include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #include<cmath> #include<stack> #include<queue> using namespace std; typedef long long ll; const int maxn = 100100; const int mod = 201314; int n,q; int h[maxn],size; struct E{ int to,next; }e[maxn]; void add_edge(int u,int v){ e[++size].to=v; e[size].next=h[u]; h[u]=size; } int rt[maxn],lc[maxn*150],rc[maxn*150],sum[maxn*150],add[maxn*150],tot; int fa[maxn],dep[maxn],sz[maxn],son[maxn]; int dfn[maxn],top[maxn],id[maxn],tim; void dfs1(int u,int par){ fa[u]=par; dep[u]=dep[par]+1; sz[u]=1; int maxs=-1; for(int i=h[u];i!=-1;i=e[i].next){ int v=e[i].to; if(v==par) continue; dfs1(v,u); sz[u]+=sz[v]; if(sz[v]>maxs){ maxs=sz[v]; son[u]=v; } } } void dfs2(int u,int par){ top[u]=par; dfn[u]=++tim; id[tim]=u; if(son[u]) dfs2(son[u],par); for(int i=h[u];i!=-1;i=e[i].next){ int v=e[i].to; if(v==fa[u]||v==son[u]) continue; dfs2(v,v); } } void build(int &i,int l,int r){ i=++tot; if(l==r) return; int mid=(l+r)/2; build(lc[i],l,mid); build(rc[i],mid+1,r); } void mdf(int &i,int l,int r,int x,int y){ sum[++tot]=sum[i],lc[tot]=lc[i],rc[tot]=rc[i],add[tot]=add[i]; i=tot; sum[i]+=(y-x+1); sum[i]%=mod; if(x==l&&r==y){ ++add[i]; return; } int mid=(l+r)/2; if(x>mid) mdf(rc[i],mid+1,r,x,y); else if(y<=mid) mdf(lc[i],l,mid,x,y); else{ mdf(lc[i],l,mid,x,mid); mdf(rc[i],mid+1,r,mid+1,y); } } int qry(int i,int ad,int l,int r,int x,int y){ if(l==x&&r==y){ return (sum[i]+1ll*ad*(r-l+1)%mod)%mod; } int mid=(l+r)/2; if(x>mid) return qry(rc[i],(ad+add[i])%mod,mid+1,r,x,y); else if(y<=mid) return qry(lc[i],(ad+add[i])%mod,l,mid,x,y); else{ return qry(lc[i],(ad+add[i])%mod,l,mid,x,mid)+qry(rc[i],ad+add[i],mid+1,r,mid+1,y); } } void upd(int i,int u,int v){ while(top[u]^top[v]){ if(dep[u]<dep[v]) swap(u,v); mdf(rt[i],1,n,dfn[top[u]],dfn[u]); u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); mdf(rt[i],1,n,dfn[u],dfn[v]); } int query(int i,int u,int v){ int res=0; while(top[u]^top[v]){ if(dep[u]<dep[v]) swap(u,v); res+=qry(rt[i],0,1,n,dfn[top[u]],dfn[u]); res%=mod; u=fa[top[u]]; } if(dep[u]>dep[v]) swap(u,v); res+=qry(rt[i],0,1,n,dfn[u],dfn[v]); res%=mod; return res; } ll read(){ ll s=0,f=1; char ch=getchar(); while(ch<'0' || ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9'){ s=s*10+ch-'0'; ch=getchar(); } return s*f; } int main(){ memset(h,-1,sizeof(h)); n=read(),q=read(); int u,v,z; for(int i=2;i<=n;i++){ u=read(); ++u; add_edge(i,u),add_edge(u,i); } dfs1(1,0); dfs2(1,1); build(rt[0],1,n); for(int i=1;i<=n;i++){ rt[i]=rt[i-1]; upd(i,1,i); } for(int i=1;i<=q;i++){ u=read()+1,v=read()+1,z=read()+1; printf("%d\n",(query(v,1,z)-query(u-1,1,z)+mod)%mod); } return 0; }