前言：

这题感觉还是很有意思。离线思路很奇妙。可能和二次离线有那么一点点相似？当然我不会二次离线我就不云了。

解析：

题目十分清真。

求一段连续区间内的所有点和某个给出的点的Lca的深度和。

首先可以转化一步。

我们可以只考虑一个询问。那么当前询问的答案可以转化为：将区间[l,r]中的每一个点到根节点的路径上的点的点权都加一。然后统计给出点z到根节点的路径上的点权之和即可。

可以使用树剖线段树搞定。

这个转化正确性显然。

但是，当考虑到多次询问时，就有点不对劲。因为两个询问如果一起计算贡献，就会算重。

比如，考虑[1,6]和[4,7]，如果先算[1,6]，那当算[4,7]时，就要先把之前线段树内的答案清空，再计算这个区间的答案。

相当于每一次询问都要清空线段树，然后重新计算。这样显然T的飞起。

那怎样才能利用之前询问的信息呢？

首先容易想到，计算一段区间的贡献，可以转化为求两个前缀的贡献之差。

然后，我们可以发现，如果计算当前区间的答案时，想使用上个区间的答案，当且仅当当前区间包含上一个区间。

那我们就可以设计出一个合理的顺序，使每个区间都能够包含之前的区间。

现在就很清晰了。

首先我们把所有询问离线下来，然后把每个询问[l,r]拆成两个区间[1,l-1]和[1,r]，按照右端点从小到大排序。最后统计答案。

然后就没啥了。注意细节。

代码

#include <bits/stdc++.h>

using namespace std;

#define int long long

typedef long long ll;

const int maxn=50000+10,mod=201314;

#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)

#define read() ({ register int x = 0, f = 1; register char c = gc(); while(c < '0' || c > '9') { if (c == '-') f = -1; c = gc();} while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc(); f * x; })

char buf[1 << 20], *p1, *p2;

struct Segment_tree{

	ll val,lazy;

}tree[maxn<<2];

struct node{

	int to,nxt;

}edge[maxn<<1];

struct que{

	int r,z,op,data;

	ll ans;

	que(){}

	que(int x,int y,int c,int d){

		r=x;

		z=y;

		op=c;

		data=d;

	}

}b[maxn<<1];

int head[maxn],depth[maxn],size[maxn],son[maxn],fa[maxn],dfn[maxn],top[maxn];

int Time,cnt,n,m,tot;

void add(int from,int to){

    edge[++cnt].to=to;

    edge[cnt].nxt=head[from];

    head[from]=cnt;

}

void dfs1(int u){

    size[u]=1;

    for(int i=head[u];i;i=edge[i].nxt){

        int v=edge[i].to;

        if(v==fa[u]) continue;

        depth[v]=depth[u]+1;

        dfs1(v);

        size[u]+=size[v];

        if(size[v]>size[son[u]]) son[u]=v;

    }

}

void dfs2(int u,int t){

    top[u]=t;

    dfn[u]=++Time;

    if(son[u]) dfs2(son[u],t);

    for(int i=head[u];i;i=edge[i].nxt){

        int v=edge[i].to;

        if(v!=fa[u]&&v!=son[u]) dfs2(v,v);

    }

}

bool cmp(que x,que y){

	return x.r<y.r ;

}

bool cmp2(que x,que y){

	return x.data!=y.data ? x.data<y.data : x.op<y.op ;

}

void pushup(int rt){

	tree[rt].val=(tree[rt<<1].val+tree[rt<<1|1].val)%mod;

}

void update(int rt,int l,int r,ll x){

	tree[rt].lazy+=x;

	if(tree[rt].lazy>=mod) tree[rt].lazy-=mod;

	tree[rt].val+=x*(r-l+1)%mod;

	if(tree[rt].val>=mod) tree[rt].val-=mod;

}

void pushdown(int rt,int l,int r){

	if(!tree[rt].lazy) return;

	int mid=(l+r)>>1;

	update(rt<<1,l,mid,tree[rt].lazy);

	update(rt<<1|1,mid+1,r,tree[rt].lazy);

	tree[rt].lazy=0;

}

void modify(int rt,int l,int r,int s,int t){

	if(s<=l&&r<=t){

		update(rt,l,r,1);

		return;

	}

	int mid=(l+r)>>1;

	pushdown(rt,l,r);

	if(s<=mid) modify(rt<<1,l,mid,s,t);

	if(t>mid) modify(rt<<1|1,mid+1,r,s,t);

	pushup(rt);

}

ll query(int rt,int l,int r,int s,int t){

	if(s<=l&&r<=t) return tree[rt].val%mod;

	int mid=(l+r)>>1;

	pushdown(rt,l,r);

	if(t<=mid) return query(rt<<1,l,mid,s,t);

	if(s>mid) return query(rt<<1|1,mid+1,r,s,t);

	return (query(rt<<1,l,mid,s,t)+query(rt<<1|1,mid+1,r,s,t))%mod;

}

void Modify(int u){

	while(top[u]!=1){

		modify(1,1,n,dfn[top[u]],dfn[u]);

		u=fa[top[u]];

	}

	modify(1,1,n,1,dfn[u]);

}

ll Query(int u){

	ll res=0;

	while(top[u]!=1){

		res+=query(1,1,n,dfn[top[u]],dfn[u]);

		if(res>=mod) res-=mod;

		u=fa[top[u]];

	}

	res+=query(1,1,n,1,dfn[u]);

	if(res>=mod) res-=mod;

	return res;

}

void Solve(){

	scanf("%lld%lld",&n,&m);

	for(int i=2;i<=n;++i){

		scanf("%lld",&fa[i]);

		fa[i]++;

		add(i,fa[i]);

		add(fa[i],i);

	}

	dfs1(1);

	dfs2(1,1);

	for(int i=1,aa,bb,cc;i<=m;++i){

		scanf("%lld%lld%lld",&aa,&bb,&cc);

		aa++;bb++;cc++;

		b[++tot]=que(aa-1,cc,0,i);

		b[++tot]=que(bb,cc,1,i);

	}

	sort(b+1,b+tot+1,cmp);

	int now=0;

	for(int i=1;i<=tot;++i){

		while(now<b[i].r){

			now++;

			Modify(now);

		}

		b[i].ans=Query(b[i].z);

	}

	sort(b+1,b+tot+1,cmp2);

	for(int i=2;i<=tot;i+=2) printf("%lld\n",(b[i].ans-b[i-1].ans+mod)%mod);

}

signed main(){

	Solve();

	return 0;

}

巴特西

[火星补锅] 非确定性有穷状态决策自动机练习题Vol.3 T3 && luogu P4211 [LNOI2014]LCA 题解

前言：

解析：

最新文章

热门文章