[CSP-S模拟测试]:影魔（树状数组+线段树合并）

题目背景

影魔，奈文摩尔，据说有着一个诗人的灵魂。事实上，他吞噬的诗人灵魂早已成千上万。
千百年来，他收集了各式各样的灵魂，包括诗人、牧师、帝王、乞丐、奴隶、罪人，当然，还有英雄。
每一个灵魂，都有着自己的战斗力，而影魔，靠这些战斗力提升自己的攻击。

题目传送门（内部题42）

输入格式

第一行两个数$n,m$。
第二行$n$个数，第$i$个数即第$i$个灵魂结点的灵魂种类$c_i$。
第三行$n-1$个数，第$i$个数表示$i+1$号灵魂结点的父亲结点。
接下来$m$行，每行两个数$u,d$，表示一组询问。

输出格式

一共$m$行，每一行一个数表示对应询问的答案。

样例

样例输入：

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

样例输出：

1
3
3
1
2

数据范围与提示

对于$30\%$的数据，$n,m\leqslant 1,000$
对于另外$10\%$的数据，保证数据随机
对于另外$20\%$的数据，每次询问满足$d={10}^9$
对于另外$20\%$的数据，满足$n,m\leqslant 20,000$
对于$100\%$的数据，满足$n,m\leqslant 100,000,c_i,n\leqslant n$

题解

我好像又没打正解……

我的思路就是，现将问题离线，然后$DFS$，每次合并儿子的，用线段树合并实现，用树状数组优化。

听着简单，但是实现起来还是蛮难的，调了好久……

不知道有什么好说的了，精髓还是在代码里。

时间复杂度：$\Theta(n\log n)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

struct rec{int nxt,to;}e[100000];

int head[100001],cnt;

int n,m;

int c[100001],f[100001];

int trs[400001],depth[100001];

int ans[100001];

vector<pair<int,int> > question[100001];

void add(int x,int y)

{

	e[++cnt].nxt=head[x];

	e[cnt].to=y;

	head[x]=cnt;

}

int lowbit(int x){return x&-x;}

void change(int x,int w){for(int i=x;i<=n;i+=lowbit(i))trs[i]+=w;}

int ask(int x){int res=0;for(int i=x;i;i-=lowbit(i))res+=trs[i];return res;}

int tr[4000001],ls[4000001],rs[4000001];

int root[200001],tot;

void insert(int &x,int k,int fl,int l,int r)

{

	if(!x)x=++tot;

	if(l==r){tr[x]=fl;change(fl,1);return;}

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

	if(k<=mid)insert(ls[x],k,fl,l,mid);

	else insert(rs[x],k,fl,mid+1,r);

}

void merge(int &x,int fl,int l,int r)

{

	if(!fl)return;

	if(!x)

	{

		x=fl;

		return;

	}

	if(l==r)

	{

		change(max(tr[x],tr[fl]),-1);

		tr[x]=min(tr[x],tr[fl]);

		return;

	}

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

	merge(ls[x],ls[fl],l,mid);

	merge(rs[x],rs[fl],mid+1,r);

}

void dfs(int x)

{

	for(int i=0;i<question[x].size();i++)

		ans[question[x][i].first]-=ask(min(depth[x]+question[x][i].second,n))-ask(depth[x]-1);

	insert(root[x],c[x],depth[x],0,n);

	for(int i=head[x];i;i=e[i].nxt)

	{

		depth[e[i].to]=depth[x]+1;

		dfs(e[i].to);

		merge(root[x],root[e[i].to],0,n);

	}

	for(int i=0;i<question[x].size();i++)

		ans[question[x][i].first]+=ask(min(depth[x]+question[x][i].second,n))-ask(depth[x]-1);

}

int main()

{

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

	for(int i=1;i<=n;i++)scanf("%d",&c[i]);

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

	{

		scanf("%d",&f[i]);

		add(f[i],i);

	}

	for(int i=1;i<=m;i++)

	{

		int u,d;

		scanf("%d%d",&u,&d);

		question[u].push_back(make_pair(i,d));

	}

	depth[1]=1;

	dfs(1);

	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);

	return 0;

}

rp++

巴特西