题解 P4211 【[LNOI2014]LCA】
紫钦
·
·
题解
这题统计l~r中所有点与z的lca的深度之和。
暴力就是把lca都求出来。。。
所以正解要么是一次求出多个lca，要么就是用玄学的方法把这个求多个deep的和转化一下。
前者我不会。
我们来看后者：
我们从整体上考虑，发现对于一个询问：l , r , z 来说，所有的 lca 都在 z 到根的路径上。**从而有一些点，它们对很多的 lca 的深度都有贡献**，而这个贡献等于在这个点下面的 lca 的个数，所以我们可以把每个 lca 到根的路径上的每个点的权值都加一。然后从 z 向上走到根，沿路统计的权值就是答案了。
**现在的问题就是：怎么找到这些 lca 并打上标记？**
~~想想当初我们不会求 lca 的时候，~~要求lca（x , y）时，我们可以将根到 x 的所有点染色，然后从 y 向上爬，爬到的第一个有颜色的点就是lca (x , y)了，我们现在也可以这么做。
就是：对于一个询问： l , r , z ，我们把每个点 i （ l <= i <= r ） 到根的路径上的每一个点的权值都加一，记得上文我写到：**所有的 lca 都在 z 到根的路径上**，所以我们可以从 z 点向上爬到根，沿途统计的点权值之和，就是答案了。
~~这样就比暴力快不了多少了。~~
***
是时候考虑优化的问题了：我们每次的操作都是从某个点到根的，所以树链剖分+线段树就好了。
但是考虑到每次统计时，不能很好的排除 l ~ r 区间之外的点对 z->根 这条路径的贡献，所以我们每次都要清空线段树。
我们每次清空线段树，然后从 l ~ r 再添加一遍，树剖+线段树的复杂度就是$O(n * logn * logn)$的，还要做 q 次，复杂度依然不理想。
***
看数据范围，$O(n*logn*logn)$应该就是正解了，现在要想办法优化掉最后的那个 q 的复杂度。
我们看到区间 l~r ，~~总要想想差分的对不对，~~想到差分可以将询问拆开，而且每个拆开的区间之间是有重叠的，是可以转移的，而不用每次都清空。
**而且差分后的数组只与右端点有关！**
**所以我们可以将差分后的区间按照右端点从小到大排序（左端点都是根），然后按从小到大的顺序添加点，每遇到一个询问就查询一次，从而排除掉区间之外的点的影响，也就优化掉一个 q 的复杂度。**
至此，思路全部结束。
***
细节：
1.树剖+线段树的细节（这里不做赘述）。
2.差分当然要标记一下这个区间是 1 ~ l-1 还是 1~r 。
3.题目是以0为根，不习惯的朋友可以整体+1。整体+1也要注意，~~我做这题时就忘了询问也加一了，~~这也是个细节。
4.似乎没什么了。。。
***
AC代码（832ms）：
关键点的注释已经写到代码里了，若还有不懂的可以私聊我。
```cpp
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int MAXN = 50005;
const int MOD = 201314;
struct Que {
int ans1,ans2; // 询问的区间的答案是ans1-ans2。
Que() {ans1=ans2=0;}
}que[MAXN];
struct Que_part { //用来做差分的询问。
int num,pos,z; // 属于第几个询问； 询问是1~pos这个区间的和； 询问的点是z。
bool flag; // 类型：0：1~l-1 ； 1：1~r。
Que_part() {num=pos=z=flag=0;}
Que_part(int a,int b,int c,bool d) {
num=a; pos=b; z=c; flag=d;
}
inline bool operator < (const Que_part &a) const {
return this->pos<a.pos;
}
}que_p[MAXN<<1];
inline bool operator > (const Que_part &a,const Que_part &b) { // 我只是想看看operator定义到外面会怎么样。
return a.pos>b.pos;
}
int n,q; // 如题。
int nex[MAXN],to[MAXN],en[MAXN]; // next; to; end; 变量名简陋，勿喷。
int size[MAXN],fa[MAXN],dep[MAXN],son[MAXN]; // size; father; deep; heavy son(姑且这么叫吧);
int top[MAXN],seq[MAXN],dfn[MAXN]; // seq是点到序列的映射，dfn是序列到点的映射。
int sum[MAXN<<2],col[MAXN<<2],nowl,nowr; // 线段树；nowl,nowr表示当前查询/修改的区间的左右端点。
void update(int rt)
{
sum[rt]=(sum[rt<<1]+sum[rt<<1|1]) %MOD;
}
/*void build(int l,int r,int rt)
{
if(l==r) {
sum[rt]=col[rt]=0;
return ;
}
col[rt]=0;
int mid=(l+r)>>1;
build(lson);
build(rson);
update(rt);
}*/
void color(int l,int r,int rt,int co)
{
sum[rt]=(sum[rt]+(r-l+1)*co) %MOD;
if(l<r) col[rt]=(col[rt]+co) %MOD;
}
void push_col(int l,int r,int rt)
{
if(col[rt] && l<r) {
int mid=(l+r)>>1;
color(lson,col[rt]);
color(rson,col[rt]);
}
col[rt]=0;
}
int query(int l,int r,int rt)
{
if(nowl<=l && r<=nowr) return sum[rt];
push_col(l,r,rt);
int mid=(l+r)>>1,ans=0;
if(nowl<=mid) ans+=query(lson);
if(mid<nowr ) ans+=query(rson);
return ans %MOD;
}
void modify(int l,int r,int rt)
{
if(nowl<=l && r<=nowr) {
color(l,r,rt,1);
return ;
}
push_col(l,r,rt);
int mid=(l+r)>>1;
if(nowl<=mid) modify(lson);
if(mid<nowr ) modify(rson);
update(rt);
}
void dfs1(int x)
{
size[x]=1;
for(int p=en[x];p;p=nex[p]) {
if(to[p]!=fa[x]) { //其实用不着判断的，但我写习惯了。
dep[to[p]]=dep[x]+1;
dfs1(to[p]);
if(size[son[x]]<size[to[p]]) son[x]=to[p];
size[x]+=size[to[p]];
}
}
}
void dfs2(int x,int anc)
{
static int t=0;
top[x]=anc;
seq[x]=++t;
dfn[t]=x;
if(!son[x]) return ;
dfs2(son[x],anc);
for(int p=en[x];p;p=nex[p]) {
if(to[p]!=fa[x] && to[p]!=son[x])
dfs2(to[p],to[p]);
}
}
int query_chain(int x,int y)
{
int tx=top[x],ty=top[y],ans=0;
while(tx!=ty) {
if(dep[tx]<dep[ty]) {
x^=y^=x^=y;
tx^=ty^=tx^=ty;
}
nowl=seq[tx];nowr=seq[x];
ans+=query(1,n,1);
x=fa[tx];
tx=top[x];
}
if(dep[x]>dep[y]) x^=y^=x^=y;
nowl=seq[x];nowr=seq[y];
ans+=query(1,n,1);
return ans %MOD;
}
void modify_chain(int x,int y)
{
int tx=top[x],ty=top[y];
while(tx!=ty) {
if(dep[tx]<dep[ty]) {
x^=y^=x^=y;
tx^=ty^=tx^=ty;
}
nowl=seq[tx];nowr=seq[x];
modify(1,n,1);
x=fa[tx];
tx=top[x];
}
if(dep[x]>dep[y]) x^=y^=x^=y;
nowl=seq[x];nowr=seq[y];
modify(1,n,1);
}
int main()
{
int l,r,z,cnt=0,now=0;
scanf("%d %d",&n,&q);
for(int i=2;i<=n;++i) { // 整体编号加一。
scanf("%d",&z);
nex[++cnt]=en[fa[i]=++z];to[cnt]=i;en[z]=cnt; // 加一条 z->i 的有向边。
}
cnt=0;
for(int i=1;i<=q;++i) {
scanf("%d %d %d",&l,&r,&z);
++r;++z;
que_p[++cnt]=Que_part(i,l,z,0);
que_p[++cnt]=Que_part(i,r,z,1);
}
dep[1]=1;
dfs1(1);
dfs2(1,1);
//build(1,n,1);// 我为什么要建树。。。
sort(que_p+1,que_p+cnt+1);
for(int i=1;i<=cnt;++i) {
while(now<que_p[i].pos) { // 一个点一个点往近添加。 now为当前添加过的点。
modify_chain(1,++now);
}
l=que_p[i].num; // 反正l没用了。就令l为当前子询问对应的母询问的序号吧。
if(que_p[i].flag) que[l].ans1=query_chain(1,que_p[i].z); // 也许不写这个1会让常数稍稍小一点。
else que[l].ans2=query_chain(1,que_p[i].z);
}
for(int i=1;i<=q;++i) {
printf("%d\n",(que[i].ans1-que[i].ans2+MOD) %MOD); // 记得要判负数。。。
}
return 0;
}
```