BZOJ4154: [Ipsc2015]Generating Synergy【KD树(懒标记)】

题目描述：

给定一棵以1为根的有根树,初始所有节点颜色为1,每次将距离节点a不超过l的a的子节点染成c,或询问点a的颜色。
T<=6,n,m,c<=10^5,1<=a<=n,0<=l<=n,0<=c<=c

题目分析：

n+e的题解：

Code：

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;
const int mod = 1e9+7;
int T,n,m,out[maxn],dfn[maxn],tim,dep[maxn];
vector<int>G[maxn];
void dfs(int u){
	dfn[u]=++tim;
	for(int i=G[u].size()-1,v;i>=0;i--) dep[v=G[u][i]]=dep[u]+1,dfs(v);
	out[u]=tim;
}
int rt,id[maxn],ans,x[2],y[2];
struct node{
	int d[2],mn[2],mx[2],ch[2],col,tag;
	void upd(node *t){
		mn[0]=mx[0]=d[0],mn[1]=mx[1]=d[1];
		for(int i=0;i<2;i++) if(ch[i])
			for(int j=0;j<2;j++) mn[j]=min(mn[j],t[ch[i]].mn[j]),mx[j]=max(mx[j],t[ch[i]].mx[j]);
	}
}t[maxn];
template<int D>bool cmp(int i,int j){return t[i].d[D]==t[j].d[D]?t[i].d[D^1]<t[j].d[D^1]:t[i].d[D]<t[j].d[D];}
bool (*fun[2])(int i,int j)={cmp<0>,cmp<1>};
void build(int &i,int l,int r,int D){
	if(l>r) return void(i=0);
	int o=(l+r)>>1;nth_element(id+l,id+o,id+r+1,fun[D]),i=id[o];
	build(t[i].ch[0],l,o-1,D^1),build(t[i].ch[1],o+1,r,D^1);
	t[i].upd(t);
}
inline void pushdown(int i){
	if(t[i].tag){
		int x=t[i].ch[0];if(x) t[x].col=t[x].tag=t[i].tag;
		if((x=t[i].ch[1])) t[x].col=t[x].tag=t[i].tag;
		t[i].tag=0;
	}
}
void cover(int i,int c){
	if(!i||x[1]<t[i].mn[0]||t[i].mx[0]<x[0]||y[1]<t[i].mn[1]||t[i].mx[1]<y[0]) return;
	if(x[0]<=t[i].mn[0]&&t[i].mx[0]<=x[1]&&y[0]<=t[i].mn[1]&&t[i].mx[1]<=y[1]) {t[i].col=t[i].tag=c;return;}
	if(x[0]<=t[i].d[0]&&t[i].d[0]<=x[1]&&y[0]<=t[i].d[1]&&t[i].d[1]<=y[1]) t[i].col=c;
	pushdown(i);
	cover(t[i].ch[0],c),cover(t[i].ch[1],c);
}
int qry(int i,int j,int D){
	if(i==j) return t[i].col;
	pushdown(i);
	return qry(t[i].ch[fun[D](i,j)],j,D^1);
}
int main()
{
	scanf("%d",&T);
	while(T--){
		scanf("%d%*d%d",&n,&m),ans=tim=0;
		for(int i=1;i<=n;i++) G[i].clear();
		for(int i=2,x;i<=n;i++) scanf("%d",&x),G[x].push_back(i);
		dfs(1);
		for(int i=1;i<=n;i++) id[i]=i,t[i].d[0]=dfn[i],t[i].d[1]=dep[i],t[i].col=1,t[i].tag=0;
		build(rt,1,n,0);
		for(int i=1,a,b,c;i<=m;i++){
			scanf("%d%d%d",&a,&b,&c);
			if(!c) ans=(ans+1ll*i*qry(rt,a,0))%mod;
			else x[0]=dfn[a],x[1]=out[a],y[0]=dep[a],y[1]=dep[a]+b,cover(rt,c);
		}
		printf("%d\n",ans);
	}
}