3626: [LNOI2014]LCA
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 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*];
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+))%MOD;
sgt[rch].sum=(sgt[rch].sum+sgt[now].lzy*(sgt[rch].r-sgt[rch].l+))%MOD;
sgt[now].lzy=;
}
}
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)>>);
Build_sgt(rch,((l+r)>>)+,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+;
sgt[now].lzy++;
return ;
}
down(now);
int mid=(sgt[now].l+sgt[now].r)>>;
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+,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)>>;
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+,r))%MOD;
}
struct Edge
{
int np;
Edge *next;
}E[MAXE],*V[MAXV];
int tope=-;
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=;
void dfs1(int now)
{
Edge *ne;
int mxsiz=;
siz[now]=;
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=;i<=n;i++)
{
scanf("%d",&x);x++;
fa[i]=x;
addedge(x,i);
}
dfs1();
top[]=;
dfs2();
Build_sgt(,,n);
for (i=;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-].push_back(make_pair(z,));
vec[y].push_back(make_pair(z,));
}
vector<pair<int,int> >::iterator it1;
for (i=;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=;i<vec[].size();i++)
{
vec[][i].second=;
}
int ans;
for (i=;i<=n;i++)
{
x=i;
while (x!=)
{
Add_sgt(,pos[top[x]],pos[x]);
x=fa[top[x]];
}
for (j=;j<vec[i].size();j++)
{
x=vec[i][j].first;
ans=;
while (x!=)
{
ans=(ans+Qry_sgt(,pos[top[x]],pos[x]))%MOD;
x=fa[top[x]];
}
vec[i][j].second=ans;
}
}
for (i=;i<m;i++)
{
ans=;
it1=lower_bound(vec[qur[i].x-].begin(),vec[qur[i].x-].end(),make_pair(qur[i].z,));
ans-=it1->second;
it1=lower_bound(vec[qur[i].y].begin(),vec[qur[i].y].end(),make_pair(qur[i].z,));
ans+=it1->second;
printf("%d\n",ans);
}
}