[题解] 动态树——KDT维护二维偏序信息

好久没写正经题解了，赶紧在退役之前写点罢。

本题来源于今天的考试。作为一个十分有版泉意识的好孩子，咱不会将题目搬上来，只提供大概题意。不过这个思路倒是非常值得学习的！

简要题意

给定一棵树，动态维护点的泉值。有以下三个操作——

在 $x$ 子树内，和 $x$ 距离小于等于 $d$ 的所有节点泉值加上 $v$
查询在 $x$ 子树内，和 $x$ 距离小于等于 $d$ 的所有节点泉值之和
新增一个节点，接在 $fa$ 下面，泉值为 $v$

思路

显然我们可以先离线询问以构建出完成所有操作 $3$ 之后的树的形态。

然后是本题的神之一笔，我们对离线树进行 dfs 记录下 dfn 序。题目的修改和查询的形式都为 “$x$ 子树内相对深度不超过 $d$”。我们发现前面一个条件可以转换为在 dfn 序上存在 $dfn_u \in [dfn_x,dfn_x+size_x-1]$，而后面一个条件则转化为 $dep_u \in [dep_x,dep_x+d]$。这是一个二维偏序的形式。

之后的处理办法我们可以看做一个套路记下来，即维护这种 $n$ 维偏序形式的信息，可以使用 K-D Tree。我们将树上的每一个点映射到二维平面上的 $(dfn_u,dep_u)$，就可以用 K-D Tree 进行维护了。

而插入操作，我们可以使用 K-D Tree 的默认插入思路，把新的节点暴力插入到一个“散块序列”中，每次维护的时候暴力维护散块的信息。散块数量到达重构因子的大小后就直接重构整颗 K-D Tree。

容易得到在 $b = \sqrt n$ 的时候理论复杂度最优。（$b$ 为重构因子大小，视 $n,q$ 同阶）不过 K-D Tree 重构的常数较大，可以适当调大重构因子。（注：该处理解有误）

UPD on 2023-11-08 21:01：这里参考了该题题解的说法，将重构视为 $O(n)$ 的，然而实际上重构应该是 $O(n \log n)$ 的，因此应当依次为根据调整重构因子大小。感谢 @ningago 的指出。

维护信息所用的 K-D Tree 和之前咱写的 K-D Tree 貌似有点不一样，它更像线段树（事实上支持区间修改也需要懒标记）。

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define Akano 1
#define pure__Elysia 0
#define loves ^
using namespace std;
using ll = long long;
constexpr int MAXN = 8e5 + 1018 + 1108;

class FastIO{//1.3
	//两百行的 FastIO 你爱吗
};
FastIO fio(stdin,stdout),ferr(nullptr,stderr);

struct Position{
	int x,y;
	Position() = default;
	Position(int _x,int _y){
		x = _x,y = _y;
		return ;
	}
}pointpos[MAXN];
struct Rectangle{
	Position l,r;
	Rectangle() = default;
	Rectangle(Position _l,Position _r){
		l = _l,r = _r;
		return ;
	}
};
inline bool Connected(const Rectangle& r1,const Rectangle& r2){
	int l,r,u,d;
	l = max(r1.l.x,r2.l.x),r = min(r1.r.x,r2.r.x);
	u = max(r1.l.y,r2.l.y),d = min(r1.r.y,r2.r.y);
	return (l <= r && u <= d);
}
inline bool Include(const Rectangle& r1,const Rectangle& r2){//r1 includes r2
	return r1.l.x <= r2.l.x && r2.r.x <= r1.r.x && r1.l.y <= r2.l.y && r2.r.y <= r1.r.y;
}
struct Edge{
	int nxt,to;
}e[MAXN * 2];
int head[MAXN],cnt;
inline void AddEdge(int from,int to){
	e[++cnt].to = to;
	e[cnt].nxt = head[from];
	head[from] = cnt;
	return ;
}
int n,orgn,q,a[MAXN],dep[MAXN],dfn[MAXN],psize[MAXN],dnt;
struct QueryType{
	int opt,x,d,v;
}query[MAXN];
void dfs(int u,int fa){
	dep[u] = dep[fa] + 1,dfn[u] = ++dnt,psize[u] = 1;
	pointpos[u] = Position(dfn[u],dep[u]);
	for(int i = head[u];i;i = e[i].nxt){
		const int v = e[i].to;
		if(v == fa)continue;
		dfs(v,u);
		psize[u] += psize[v];
	}
	return ;
}
struct Node{
	Rectangle rect;
	int l,r,siz;
	ll val,lazy;
	Node() = default;
	Node(Rectangle _rect,int _val){
		rect = _rect;
		l = r = 0,siz = 1;
		val = _val,lazy = 0;
		return ;
	}
}node[MAXN * 4];
bool CmpX(Node n1,Node n2){
	if(n1.rect.l.x != n2.rect.l.x)return n1.rect.l.x < n2.rect.l.x;
	return n1.rect.l.y < n2.rect.l.y;
}
bool CmpY(Node n1,Node n2){
	if(n1.rect.l.y != n2.rect.l.y)return n1.rect.l.y < n2.rect.l.y;
	return n1.rect.l.x < n2.rect.l.x;
}
class KDTree{
private:
	int root,tot;
	vector<Node> resNode,insNode;//散点 和 插入暂用的序列
	inline void PushUp(int p){
		node[p].val = node[node[p].l].val + node[node[p].r].val;
		node[p].siz = node[node[p].l].siz + node[node[p].r].siz;
		return ;
	}
	inline void Add(int p,ll val){
		if(!p)return ;
		node[p].val += node[p].siz * val;
		node[p].lazy += val;
		return ;
	}
	inline void PushDown(int p){
		if(node[p].lazy == 0)return ;
		Add(node[p].l,node[p].lazy),Add(node[p].r,node[p].lazy);
		node[p].lazy = 0;
		return ;
	}
	void Build(int& p,int l,int r,bool W){
		if(p == 0)p = ++tot;
		node[p].l = node[p].r = node[p].lazy = 0;
		if(l == r){
			node[p] = insNode[l];
			return ;
		}
		const int mid = (l + r) >> 1;
		if(W){
			nth_element(insNode.begin()+l,insNode.begin()+mid,insNode.begin()+r,CmpX);
		}else{
			nth_element(insNode.begin()+l,insNode.begin()+mid,insNode.begin()+r,CmpY);
		}
		Build(node[p].l,l,mid,!W),Build(node[p].r,mid+1,r,!W);
		PushUp(p);
		node[p].rect.l.x = min(node[node[p].l].rect.l.x,node[node[p].r].rect.l.x);
		node[p].rect.l.y = min(node[node[p].l].rect.l.y,node[node[p].r].rect.l.y);
		node[p].rect.r.x = max(node[node[p].l].rect.r.x,node[node[p].r].rect.r.x);
		node[p].rect.r.y = max(node[node[p].l].rect.r.y,node[node[p].r].rect.r.y);
		return ;
	}
	inline void ReBuild(){
		swap(insNode,resNode);
		resNode.clear();
		insNode.insert(insNode.begin(),Node());
		for(int i = 1;i <= tot;i++){
			if(node[i].siz == 1){
				insNode.push_back(node[i]);
			}else{
				PushDown(i);//按照顺序PushDown
			}
		}
		root = tot = 0,size = dsize;
		Build(root,1,size,true);
		return ;
	}
	void Change(int p,const Rectangle& OBJ,ll val){
		if(!p)return ;
		if(Connected(OBJ,node[p].rect) == false)return ;
		if(Include(OBJ,node[p].rect)){
			return Add(p,val);
		}
		PushDown(p);
		Change(node[p].l,OBJ,val),Change(node[p].r,OBJ,val);
		PushUp(p);
		return ;
	}
	ll Query(int p,const Rectangle& OBJ){
		if(!p)return 0;
		if(Connected(OBJ,node[p].rect) == false)return 0;
		if(Include(OBJ,node[p].rect)){
			return node[p].val;
		}
		PushDown(p);
		ll ret = 0;
		ret += Query(node[p].l,OBJ) + Query(node[p].r,OBJ);
		return ret;
	}
public:
	int size,dsize,block;
	inline void Build(){
		size = dsize = orgn;
		root = tot = 0;
		insNode.clear();
		insNode.emplace_back(Rectangle(Position(2006,1018),Position(2006,1108)),1314);
		for(int i = 1;i <= orgn;i++){
			insNode.emplace_back(Rectangle(pointpos[i],pointpos[i]),a[i]);
		}
		assert(int(insNode.size()) == size + 1);
		Build(root,1,orgn,true);
		return ;
	}
	inline void Insert(Position pos,int val){
		resNode.emplace_back(Rectangle(pos,pos),val);
		dsize++;
		if(int(resNode.size()) >= block){
			ReBuild();
		}
		return ;
	}
	inline void Change(const Rectangle& OBJ,int val){
		Change(root,OBJ,val);
		for(auto& i : resNode){
			if(Include(OBJ,i.rect)){
				i.val += val;
			}
		}
		return ;
	}
	inline ll Query(const Rectangle& OBJ){
		ll ret = Query(root,OBJ);
		for(auto i : resNode){
			if(Include(OBJ,i.rect)){
				ret += i.val;
			}
		}
		return ret;
	}
}kdt;
int main(){
	fio>>n>>q;
	kdt.block = sqrt(n) * 2.5;
	orgn = n;
	for(int i = 1;i <= n;i++){
		fio>>a[i];
	}
	for(int i = 2,fa;i <= n;i++){
		fio>>fa;
		AddEdge(fa,i),AddEdge(i,fa);
	}
	for(int i = 1;i <= q;i++){
		fio>>query[i].opt;
		if(query[i].opt == 1){
			fio>>query[i].x>>query[i].d>>query[i].v;
		}else if(query[i].opt == 2){
			fio>>query[i].x>>query[i].d;
		}else if(query[i].opt == 3){
			fio>>query[i].x>>query[i].v;
			n++;
			AddEdge(n,query[i].x),AddEdge(query[i].x,n);
		}
	}
	dfs(1,0);
	kdt.Build();
	n = orgn;
	for(int i = 1;i <= q;i++){
		if(query[i].opt == 1){
			const int u = query[i].x,stD = dep[u],edD = dep[u] + query[i].d;
			kdt.Change(Rectangle(Position(dfn[u],stD),Position(dfn[u] + psize[u] - 1,edD)),query[i].v);
		}else if(query[i].opt == 2){
			const int u = query[i].x,stD = dep[u],edD = dep[u] + query[i].d;
			cout<<kdt.Query(Rectangle(Position(dfn[u],stD),Position(dfn[u] + psize[u] - 1,edD)))<<'\n';
		}else if(query[i].opt == 3){
			n++;
			kdt.Insert(pointpos[n],query[i].v);
		}
	}
	return not(Akano loves pure__Elysia);
}

[题解] 动态树——KDT维护二维偏序信息

简要题意

思路

代码

你真的懂模拟退火吗？「上」

[题解]U379641 少女，台阶与一切的开始

Comments NOTHING

取消回复