[LNOI2014]LCA(树链剖分)
题目:给你一棵树，给你n个询问，每个询问要求输出$sum_{i=l}^{r}depth(LCA(i,z))$
细看看其实没有想象的那么难
大体思路:
1、对于每个询问，考虑打差分变成$sum_{i=0}^{r}depth(LCA(i,z))-sum_{i=0}^{l-1}depth(LCA(i,z))$
2、那么这里就是一个思考点了
如何表示$sum_{i=0}^{p}depth(LCA(i,z))$?
我也不知道
这种时候就该换一个角度思考了
啥是深度?
不就是从根到他有几个点嘛
对于两个点i,j
从i向根的路径上+1
那么$query(root,j)$就是要求的$dep(LCA(i,j))$了
到这里思路就差不多出来了
①把每个询问分成两个，打差分
②排序询问，逐个插入$add(i,root,1)$
③每个询问查出$query(z,root)$
好了答案出来了
#include<cstdio> #include<algorithm> using std::sort; #define mo 201314 void MOD(int &a){a=(a+mo*2)%mo;} int n,m; struct sumireko { int to,ne; }e[100011]; int he[50011],ecnt; void addline(int f,int t) { e[++ecnt].to=t; e[ecnt].ne=he[f]; he[f]=ecnt; } int fa[50011],hop[50011],size[50011],dson[50011],llen[50011],dep[50011],idn[50011],idnar; void dfs1(int x) { size[x]=1; int lin=-1; for(int i=he[x],t;i;i=e[i].ne) { t=e[i].to; dfs1(t); size[x]+=size[t]; if(lin<size[t]) { lin=size[t]; dson[x]=t; } } } void dfs2(int x,int top) { idn[x]=++idnar; hop[x]=top; llen[top]++; if(!dson[x]) return; dfs2(dson[x],top); for(int i=he[x],t;i;i=e[i].ne) { t=e[i].to; if(t==dson[x]) continue; dfs2(t,t); } } struct usami { int f,id,r,z; void set(int u,int i,int o,int p){f=u,id=i,r=o,z=p;} bool friend operator < (usami a,usami b) { return a.r<b.r; } }qqq[100011]; int qcnt; int ans[50011]; struct segtree { int v[200011],del[200011],size[200011]; void build(int px,int pl,int pr) { if(pl==pr) { size[px]=1; return; } int mid=(pl+pr)>>1; build(px<<1,pl,mid); build(px<<1|1,mid+1,pr); size[px]=size[px<<1]+size[px<<1|1]; } void fuckup(int px,int pl,int pr) { if(pl==pr) return; v[px]=v[px<<1]+v[px<<1|1]; MOD(v[px]); } void fuckdown(int px,int pl,int pr) { if(pl==pr) return; if(del[px]) { v[px<<1]+=del[px]*size[px<<1];MOD(v[px<<1]); del[px<<1]+=del[px];MOD(del[px<<1]); v[px<<1|1]+=del[px]*size[px<<1|1];MOD(v[px<<1|1]); del[px<<1|1]+=del[px];MOD(del[px<<1|1]); del[px]=0; } } void add(int px,int pl,int pr,int vin,int ql,int qr) { if(ql<=pl&&qr>=pr) { v[px]+=vin*size[px]; del[px]+=vin; MOD(v[px]); MOD(del[px]); return; } fuckdown(px,pl,pr); int mid=(pl+pr)>>1; if(ql<=mid) add(px<<1,pl,mid,vin,ql,qr); if(qr>mid) add(px<<1|1,mid+1,pr,vin,ql,qr); fuckup(px,pl,pr); } int query(int px,int pl,int pr,int ql,int qr) { if(ql<=pl&&qr>=pr) return v[px]; fuckdown(px,pl,pr); int mid=(pl+pr)>>1; int ret=0; if(ql<=mid) ret+=query(px<<1,pl,mid,ql,qr),MOD(ret); if(qr>mid) ret+=query(px<<1|1,mid+1,pr,ql,qr),MOD(ret); return ret; } }tr; void inp(int x) { while(hop[x]!=hop[0]) { tr.add(1,1,n,1,idn[hop[x]],idn[x]); x=fa[hop[x]]; } tr.add(1,1,n,1,idn[0],idn[x]); } void qq(int x,int id,int f) { int prt=0; while(hop[x]!=hop[0]) { prt+=tr.query(1,1,n,idn[hop[x]],idn[x]); MOD(prt); x=fa[hop[x]]; } prt+=tr.query(1,1,n,idn[0],idn[x]); MOD(prt); ans[id]+=f*prt; MOD(ans[id]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<n;i++) scanf("%d",&fa[i]),addline(fa[i],i); dep[0]=1; dfs1(0); dfs2(0,0); tr.build(1,1,n); for(int i=1,lin,rin,zin;i<=m;i++) { scanf("%d%d%d",&lin,&rin,&zin); qqq[++qcnt].set(-1,i,lin-1,zin); qqq[++qcnt].set(1,i,rin,zin); } sort(qqq+1,qqq+qcnt+1); int tinar=-1; for(int i=1;i<=qcnt;i++) { while(tinar<qqq[i].r) {tinar++;inp(tinar);} qq(qqq[i].z,qqq[i].id,qqq[i].f); } for(int i=1;i<=m;i++) printf("%d ",ans[i]); return 0; }