LNOI2014 LCA

人生中第一道黑题

题目描述

给出一个n个节点的有根树（编号为0到n-1，根节点为0）。一个点的深度定义为这个节点到根的距离+1。 设表示点的深度，表示与的最近公共祖先。 有q次询问，每次询问给出 ，求

输入输出格式

输入格式：

第一行2个整数n q。 接下来n-1行，分别表示点1到点n-1的父节点编号。 接下来q行，每行3个整数l r z。

输出格式：

输出q行，每行表示一个询问的答案。每个答案对201314取模输出

输入输出样例

输入样例#1：

5 2
0
0
1
1
1 4 3
1 4 2

输出样例#1：

8
5

说明

共5组数据，n与q的规模分别为10000,20000,30000,40000,50000。

显然暴力的复杂度是承受不了的,上来dfs肯定是不可行的.

首先考虑两个点的lca的深度的另外一中计算方法:

利用树剖+线段树把一个点到根节点的链上点权全部+1,深度即为另一点到根节点的链的点权之和

这个方法在直接求lca时显然是大材小用,200+行的代码只是为了求个lca的深度显然得不偿失.

但是这种方法在处理本题是很有用的方法,因为这种方法可以很方便的实现对区间求lca深度之和的操作.

如图,假如要求(红色点,橙色点)和棕色点的lca的深度之和,可以这样操作:

(,分别为树剖中链增加,链查询函数)

1.poadd(R,0);
//这时poque(B,0)即为棕色点与红色点LCA的深度,即为2
2.poadd(Y,0);
3.poque(B,0);即为所求,即为3.

但是此时如果针对每一个操作都在线计算的话,复杂度仍不能达到要求.

这时注意到如果按顺序进行的操作,所有区间所需的数据都已经计算出来,即考虑差分.

采用离线算法,将所有查询全部读入后,在和处分别打上起始标记和结束标记,然后按顺序执行的操作,若发现有标记,则在对应该查询的数组存此时的值,为了差分,起始和结束可以分开记录.

这是差分部分的代码,利用vector来给每一个点记录标记,用st[i],ed[i]表示第i次查询的差分起始数据和差分终止数据.

for(int i = 0;i < N;i++)
	{
		poadd(0,i);
		for(int j = 0;j < stb[i].size();j++)
		{
			st[stb[i][j]] = poque(0,z[stb[i][j]]);
		}
		for(int j = 0;j < edb[i].size();j++)
		{
			ed[edb[i][j]] = poque(0,z[edb[i][j]]);
		}
	}

最后输出每一次查询ed[i]-st[i]即可.

本来一中午一个多小时就写完了代码,但是因为我太弱了,复制了lzydalao少了一个=的读入优化,三天没改出来...(还是我太弱了)

知道明明输出q行却一直提示Too Many or Too few Lines有多么抑郁吗,特别是在各种环境测试都没错的时候.

究其根本原因还是我太弱了

完整代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define lson (o << 1)
#define rson (o << 1|1)
#define mid ((l+r)>>1)
#define MAXN 50005
#define m 201314
using namespace std;
int fa[MAXN],son[MAXN],siz[MAXN];
int l[MAXN],dep[MAXN],top[MAXN];
vector<int> stb[MAXN],edb[MAXN];
int st[MAXN],ed[MAXN];
int N,M,R;
int z[MAXN];
struct Edge{
	int to,ne;
}e[MAXN *2];
struct Segtree
{
	int val,lazy;
}tree[MAXN*4];
int head[MAXN];
int ecnt = 0;
void addedge(int x,int y)
{
	e[++ecnt].to = y;
	e[ecnt].ne = head[x];
	head[x] = ecnt;
	return;
}
void pushdown(int l,int r,int o)
{
	tree[lson].val += (mid-l+1)*tree[o].lazy%m;
	tree[lson].lazy += tree[o].lazy%m;
	tree[rson].val += (r-mid)*tree[o].lazy%m;
	tree[rson].lazy += tree[o].lazy%m;
	tree[o].lazy = 0;
	return;
}
void update(int ql,int qr,int l,int r,int o)
{
	if(ql > r || qr <l)
	{
		return;
	}
	if(ql <= l && qr >= r)
	{
		tree[o].lazy += 1;
		tree[o].val += (r-l+1);
		return;
	}
	pushdown(l,r,o);
	update(ql,qr,l,mid,lson);
	update(ql,qr,mid+1,r,rson);
	tree[o].val = (tree[lson].val%m + tree[rson].val%m)%m;
	return;
}
int query(int ql,int qr,int l,int r,int o)
{
	if(ql > r || qr < l)
	{
		return 0;
	}
	if(qr >= r && ql <= l)
	{
		return tree[o].val;
	}
	pushdown(l,r,o);
	return (query(ql,qr,l,mid,lson)%m + query(ql,qr,mid+1,r,rson)%m)%m;
}
void dfs1(int x)
{
	siz[x] = 1;
	for(int i = head[x];i;i=e[i].ne)
	{
		int to = e[i].to;
		if(to == fa[x])
		{
			continue;
		}
		if(son[x] = -1)son[x] = to;
		else if(siz[to] > siz[son[x]])
		{
			son[x] = to;
		}
		fa[to] = x;
		dep[to] = dep[x]+1;
		dfs1(to);
		siz[x] +=siz[to];
	}
	return;
}
int xu = 0;
void dfs2(int x,int ttop)
{
	//cout << x << endl;
	l[x] = ++xu;
	top[x] = ttop;
	if(son[x] != -1)
		dfs2(son[x],ttop);
	for(int i = head[x];i;i = e[i].ne)
	{
		int to = e[i].to;
		if(to == son[x] || to == fa[x])
		{
			continue;
		}
		dfs2(to,to);
	}
	return;
}
inline void mswap(int &a,int &b)
{
	int t = a;
	a = b;
	b = t;
	return;
}
void poadd(int x,int y)
{
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])
		{
			mswap(x,y);
		}
		update(l[top[x]],l[x],1,N,1);
		x = fa[top[x]];
	}
	if(dep[x] < dep[y])
	{
		mswap(x,y);
	}
	update(l[y],l[x],1,N,1);
	return;
}
int poque(int x,int y)
{
	int ans = 0;
	while(top[x] != top[y])
	{
		if(dep[top[x]] < dep[top[y]])
		{
			mswap(x,y);
		}
		ans += query(l[top[x]],l[x],1,N,1);
		ans = ans%m;
		x = fa[top[x]];
	}
	if(dep[x] < dep[y])
	{
		mswap(x,y);
	}
	ans += query(l[y],l[x],1,N,1);
	ans %= m;
	return ans;
}
void read(int &s)
{
	s=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
	return;
}
int fm(int a)
{
	int s = a;
	while(s<0)s+=m;
	return s;
}
int main()
{
	//freopen("4211.in","r",stdin);
	memset(siz,0,sizeof(siz));
	memset(top,-1,sizeof(top));
	memset(son,-1,sizeof(son));
	memset(l,0,sizeof(l));
	memset(dep,0,sizeof(dep));
	memset(fa,-1,sizeof(fa));
	read(N);read(M);
	R = 0;
	for(int i = 1;i <= N-1;i++)
	{
		int ed;
		read(ed);
		addedge(i,ed);
		addedge(ed,i);
	}
	for(int i = 0;i < M;i++)
	{
		int op,ed;
		read(op);
		read(ed);
		read(z[i]);
		stb[op-1].push_back(i);
		edb[ed].push_back(i);
	}
	dfs1(R);
	//cout << "1!" << endl;
	dfs2(R,R);
	//cout << "2!" << endl;
	for(int i = 0;i < N;i++)
	{
		poadd(0,i);
		for(int j = 0;j < stb[i].size();j++)
		{
			st[stb[i][j]] = poque(0,z[stb[i][j]]);
		}
		for(int j = 0;j < edb[i].size();j++)
		{
			ed[edb[i][j]] = poque(0,z[edb[i][j]]);
		}
	}
	for(int i = 0;i < M-1;i++)
	{
		printf("%d\n",fm(ed[i]-st[i]));
	}
	printf("%d",fm(ed[M-1]-st[M-1]));
	//cout << poque(0,4);
}

2018-3-9 0:31:37 AC

2018-3-9 1:20:30

我要猝死了.