首页 > 代码库 > bzoj 3626: [LNOI2014]LCA 离线+树链剖分
bzoj 3626: [LNOI2014]LCA 离线+树链剖分
3626: [LNOI2014]LCA
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 426 Solved: 124
[Submit][Status]
Description
给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。
设dep[i]表示点i的深度，LCA(i,j)表示i与j的最近公共祖先。
有q次询问，每次询问给出l r z，求sigma_{l<=i<=r}dep[LCA(i,z)]。
（即，求在[l,r]区间内的每个节点i与z的最近公共祖先的深度之和）
Input
第一行2个整数n q。
接下来n-1行，分别表示点1到点n-1的父节点编号。
接下来q行，每行3个整数l r z。
Output
输出q行，每行表示一个询问的答案。每个答案对201314取模输出
Sample Input
5 2
0
0
1
1
1 4 3
1 4 2
0
0
1
1
1 4 3
1 4 2
Sample Output
8
5
5
HINT
共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。
真是不知道那些人是如何想到这道题正解的，首先，区间查询都可以转化为前缀和的差值（就这个我都没想到），然后前缀和就想到了离线，按照点编号加点，查询[1,a]与z的答案，可以将z至根的路径赋值为1，询问[1,a]每个点到更路径点权和，而本题最神奇的地方是可以转化为将[1,a]所有点到根路径点权加1，询问z至根的点权和。
#include<iostream>#include<cstdio>#include<vector>#include<cstring>#include<algorithm>using namespace std;#define MAXN 51100#define MAXE MAXN*2#define MAXQ MAXN#define MAXV MAXN#define MOD 201314#define lch (now<<1)#define rch (now<<1^1)int n,m;struct sgt_node{ int l,r,sum,lzy;}sgt[MAXN*4];void up(int now){ if (sgt[now].l==sgt[now].r)return; sgt[now].sum=(sgt[lch].sum+sgt[rch].sum)%MOD;}void down(int now){ if (sgt[now].l==sgt[now].r)return; if (sgt[now].lzy) { sgt[lch].lzy+=sgt[now].lzy; sgt[rch].lzy+=sgt[now].lzy; sgt[lch].sum=(sgt[lch].sum+sgt[now].lzy*(sgt[lch].r-sgt[lch].l+1))%MOD; sgt[rch].sum=(sgt[rch].sum+sgt[now].lzy*(sgt[rch].r-sgt[rch].l+1))%MOD; sgt[now].lzy=0; }}void Build_sgt(int now,int l,int r){ sgt[now].l=l; sgt[now].r=r; if (l==r) { return ; } Build_sgt(lch,l,(l+r)>>1); Build_sgt(rch,((l+r)>>1)+1,r);}void Add_sgt(int now,int l,int r){ if (sgt[now].l==l && sgt[now].r==r) { sgt[now].sum+=sgt[now].r-sgt[now].l+1; sgt[now].lzy++; return ; } down(now); int mid=(sgt[now].l+sgt[now].r)>>1; if (r<=mid) { Add_sgt(lch,l,r); }else if (mid<l) { Add_sgt(rch,l,r); }else { Add_sgt(lch,l,mid); Add_sgt(rch,mid+1,r); } up(now);}int Qry_sgt(int now,int l,int r){ if (sgt[now].l==l && sgt[now].r==r) { return sgt[now].sum%MOD; } int mid=(sgt[now].l+sgt[now].r)>>1; down(now); if (r<=mid) return Qry_sgt(lch,l,r); if (mid<l) return Qry_sgt(rch,l,r); return (Qry_sgt(lch,l,mid)+Qry_sgt(rch,mid+1,r))%MOD;}struct Edge{ int np; Edge *next;}E[MAXE],*V[MAXV];int tope=-1;void addedge(int x,int y){ E[++tope].np=y; E[tope].next=V[x]; V[x]=&E[tope];}int siz[MAXN];int depth[MAXN];int son[MAXN];int fa[MAXN];int top[MAXN];int pos[MAXN],dfstime=0;void dfs1(int now){ Edge *ne; int mxsiz=0; siz[now]=1; for (ne=V[now];ne;ne=ne->next) { dfs1(ne->np); siz[now]+=siz[ne->np]; if (siz[ne->np]>mxsiz) { mxsiz=siz[ne->np]; son[now]=ne->np; } }}void dfs2(int now){ Edge *ne; pos[now]=++dfstime; if (son[now]) { top[son[now]]=top[now]; dfs2(son[now]); } for (ne=V[now];ne;ne=ne->next) { if (ne->np==son[now])continue; top[ne->np]=ne->np; dfs2(ne->np); }}int q[MAXN];struct qur_t{ int x,y,z; int ans;}qur[MAXQ];vector<pair<int,int> > vec[MAXN];int main(){ freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); int x,y,z,i,j,k; scanf("%d%d",&n,&m); for (i=2;i<=n;i++) { scanf("%d",&x);x++; fa[i]=x; addedge(x,i); } dfs1(1); top[1]=1; dfs2(1); Build_sgt(1,1,n); for (i=0;i<m;i++) { scanf("%d%d%d",&x,&y,&z); x++;y++;z++; qur[i].x=x; qur[i].y=y; qur[i].z=z; vec[x-1].push_back(make_pair(z,0)); vec[y].push_back(make_pair(z,0)); } vector<pair<int,int> >::iterator it1; for (i=0;i<=n;i++) { sort(vec[i].begin(),vec[i].end()); it1=unique(vec[i].begin(),vec[i].end()); while (vec[i].end()!=it1)vec[i].pop_back(); } for (i=0;i<vec[0].size();i++) { vec[0][i].second=0; } int ans; for (i=1;i<=n;i++) { x=i; while (x!=0) { Add_sgt(1,pos[top[x]],pos[x]); x=fa[top[x]]; } for (j=0;j<vec[i].size();j++) { x=vec[i][j].first; ans=0; while (x!=0) { ans=(ans+Qry_sgt(1,pos[top[x]],pos[x]))%MOD; x=fa[top[x]]; } vec[i][j].second=ans; } } for (i=0;i<m;i++) { ans=0; it1=lower_bound(vec[qur[i].x-1].begin(),vec[qur[i].x-1].end(),make_pair(qur[i].z,0)); ans-=it1->second; it1=lower_bound(vec[qur[i].y].begin(),vec[qur[i].y].end(),make_pair(qur[i].z,0)); ans+=it1->second; printf("%d\n",ans); }}
bzoj 3626: [LNOI2014]LCA 离线+树链剖分
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。