NKOJ 4345 （Ipsc2015）Generating Synergy （DFS序+kd树）

发表于 |
字数统计: 1,132字 | 阅读时长 ≈ 6min

P4345[Ipsc2015]Generating Synergy

问题描述

给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色

输入格式

第一行一个数T,表示数据组数

接下来每组数据的第一行三个数n,c,q表示结点个数,颜色数和操作数

接下来一行n-1个数描述2..n的父节点

接下来q行每行三个数a,l,c

若c为0,表示询问a的颜色

否则将距离a不超过l的a的子节点染成c

输出格式

设当前是第i个操作,y_i为本次询问的答案(若本次操作是一个修改则y_i为0),令z_i=i*y_i,请输出z_1+z_2+…+z_q模10^9+7

样例输入

1
4 3 7
1 2 2
3 0 0
2 1 3
3 0 0
1 0 2
2 0 0
4 1 1
4 0 0

样例输出

32

提示

第1,3,5,7的询问的答案分别为1,3,3,1,所以答案为 11+20+33+40+53+60+7*1=32.

数据范围:

对于100%的数据T<=6,n,m,c<=10^5,

1<=a<=n,0<=l<=n,0<=c<=c

首先求出这棵树的DFS序和每个节点的深度，那么将DFS序的$In$作为$x$坐标，将深度作为$y$坐标，建立kd树，那么每次询问直接找对应点，修改就变成将以$(In[a],dep[a])$，$(Out[a],dep[a]+l)$为左上和右下顶点的矩形区域整体修改，kd树+lazy即可解决。

另外，也可以用树套树维护，但显然不如kd树好写。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 222222
#define ll long long
using namespace std;
int rt,D,T,n,c,q,x1,x2,y1,y2;
int L[N],R[N],dep[N],VT,mod=1e9+7;
int LA[N],NE[N],EN[N],TOT;
struct node
{
	int d[2],x[2],y[2],son[2],v,lazy;
	bool operator<(const node &b)const
	{return d[D]<b.d[D];}
}kdt[N];
void PD(int p)
{
	int ls=kdt[p].son[0],rs=kdt[p].son[1];
	kdt[ls].v=kdt[rs].v=kdt[p].lazy;
	kdt[ls].lazy=kdt[rs].lazy=kdt[p].lazy;
	kdt[p].lazy=0;
}
void MT(int p,int s)
{
	kdt[p].x[0]=min(kdt[p].x[0],kdt[s].x[0]);
	kdt[p].x[1]=max(kdt[p].x[1],kdt[s].x[1]);
	kdt[p].y[0]=min(kdt[p].y[0],kdt[s].y[0]);
	kdt[p].y[1]=max(kdt[p].y[1],kdt[s].y[1]);
}
int BT(int l,int r,int d)
{
	D=d;int o=l+r>>1;
	kdt[o].v=1;
	kdt[o].x[0]=kdt[o].x[1]=kdt[o].d[0];
	kdt[o].y[0]=kdt[o].y[1]=kdt[o].d[1];
	if(l<o)kdt[o].son[0]=BT(l,o-1,d^1),MT(o,kdt[o].son[0]);
	if(o<r)kdt[o].son[1]=BT(o+1,r,d^1),MT(o,kdt[o].son[1]);
	return o;
}
void ADD(int x,int y)
{
	TOT++;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void DFS(int x,int f)
{
	L[x]=++VT;dep[x]=dep[f]+1;
	for(int i=LA[x];i;i=NE[i])DFS(EN[i],x);
	R[x]=VT;
}
int GA(int p)
{
	if(kdt[p].lazy)PD(p);
	if(kdt[p].d[0]==x1&&kdt[p].d[1]==y1)return kdt[p].v;
	int s=0,ls=kdt[p].son[0],rs=kdt[p].son[1];
	if(kdt[ls].x[0]<=x1&&kdt[ls].x[1]>=x1&&kdt[ls].y[0]<=y1&&kdt[ls].y[1]>=y1)s+=GA(ls);
	if(kdt[rs].x[0]<=x1&&kdt[rs].x[1]>=x1&&kdt[rs].y[0]<=y1&&kdt[rs].y[1]>=y1)s+=GA(rs);
	return s;
}
void CHA(int p,int k)
{
	if(kdt[p].lazy)PD(p);
	if(kdt[p].d[0]<=x2&kdt[p].d[0]>=x1&&kdt[p].d[1]<=y2&&kdt[p].d[0]>=y1)kdt[p].v=k;
	if(kdt[p].x[0]>x2||kdt[p].x[1]<x1||kdt[p].y[0]>y2||kdt[p].y[1]<y1)return;
	if(kdt[p].x[1]<=x2&&kdt[p].x[0]>=x1&&kdt[p].y[1]<=y2&&kdt[p].y[0]>=y1){kdt[p].v=kdt[p].lazy=k;return;}
	CHA(kdt[p].son[0],k);CHA(kdt[p].son[1],k);
}
int main()
{
	int i,k,x,y;ll ans;
	scanf("%d",&T);
	while(T--)
	{
		TOT=VT=ans=0;
		memset(kdt,0,sizeof(kdt));
		memset(LA,0,sizeof(LA));
		scanf("%d%d%d",&n,&c,&q);
		for(i=2;i<=n;i++)scanf("%d",&x),ADD(x,i);
		DFS(1,0);
		for(i=1;i<=n;i++)kdt[i].d[0]=L[i],kdt[i].d[1]=dep[i];
		rt=BT(1,n,0);
		for(i=1;i<=q;i++)
		{
			scanf("%d%d%d",&x,&y,&k);
			if(k==0)
			{
				x1=L[x];y1=dep[x];
				ans=(ans+1ll*GA(rt)*i)%mod;
			}
			else
			{
				x1=L[x];x2=R[x];
				y1=dep[x];y2=dep[x]+y;
				CHA(rt,k);
			}
		}
		printf("%lld\n",ans);
	}
}