CF757G Can Bash Save the Day?

https://www.luogu.com.cn/problem/CF757G

可持久化点分树

首先一个暴力的想法就是点分树上每个点开一个线段树，下标是那个排列 \(p\) 的下标，维护个数和距离和
但发现这样空间就变成 \(O(n\log ^2 n)\) 了，而且有修改，不能像开店那个题那样简化成 vector 上二分
卡空间的话把线段树改成平衡树，常数变大，但感觉 5s 还是可过

来个不那么暴力的做法
由于区间询问可以差分，考虑给每个前缀维护一个点分树
修改的时候，就从点分树的根开始，每次把上一个前缀这个位置的节点复制过来，把个数、距离和修改掉，儿子们等信息不变
同样有点分树常见的那个容斥
然而发现每个点最多会有 \(O(n)\) 个儿子，这样一复制就爆炸了，所以先给原树转化为二叉树，再给这个二叉树建点分树
这样建完点分树上一个点最多会有 \(3\) 个儿子
于是时空都是 \(O(n\log n)\) 了

转二叉树的过程见代码

#define N 400006
#define M 800006
#define LOG_N 20
int lg2[N*2];
struct GraphT{
	int fir[N],nex[M],to[M],w[M],tot;
	inline void add(int u,int v,int c,int flag=1){
		to[++tot]=v;nex[tot]=fir[u];fir[u]=tot;w[tot]=c;
		if(flag) add(v,u,c,0);
	}
	inline void clear(){std::memset(fir,0,sizeof fir);tot=0;}
	int st[LOG_N+2][N*2],id[N*2];
	int deep[N],dfscnt,dfn[N];
	long long sum[N];
	void dfs(int u,int fa=0){
		deep[u]=deep[fa]+1;dfn[u]=++dfscnt;id[dfscnt]=u;
		for(int v,i=fir[u];i;i=nex[i]){
			v=to[i];
			if(v==fa) continue;
			sum[v]=sum[u]+w[i];
			dfs(v,u);id[++dfscnt]=u;
		}
	}
	inline void initLca(){
		dfs(1);st[0][1]=id[1];
		for(int i=2;i<=dfscnt;i++) lg2[i]=lg2[i>>1]+1,st[0][i]=id[i];
		for(int j=1;j<=LOG_N;j++)for(int i=1;i+(1<dfn[v]) lib::swap(u,v);
		u=dfn[u];v=dfn[v];
		int o=lg2[v-u+1];
		return deep[st[o][u]] G
int n;
int root,size[N],maxson[N],vis[N];
void findRoot(int u,int fa=0){
	size[u]=1;maxson[u]=0;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(v==fa||vis[v]) continue;
		findRoot(v,u);size[u]+=size[v];
		lib::chkMax(maxson[u],size[v]);
	}
	lib::chkMax(maxson[u],size[0]-size[u]);
	if(maxson[u]sonId[N];
inline void New(Node *&x){x=totAddr++;}
void divide(int u,Node *now,int tot){
	vis[u]=1;now->id=u;
	Node *nex;
	for(int v,i=G.fir[u];i;i=G.nex[i]){
		v=G.to[i];
		if(vis[v]) continue;
		root=0;size[0]=size[v]>size[u]?(tot-size[u]):size[v];
		findRoot(v);newFa[root]=u;deep[root]=deep[u]+1;	
		for(int j=0;json[0]) now->son[0]=nex,sonId[root].push_back(0);
		else if(!now->son[1]) now->son[1]=nex,sonId[root].push_back(1);
		else now->son[2]=nex,sonId[root].push_back(2);
		divide(root,nex,size[v]);
	}
}
int deg[N],totNode;
void rebuild(int u,int fa=0){
	for(int last=0,tmp=0,v,i=T.fir[u];i;i=T.nex[i]){
		v=T.to[i];
		if(v==fa) continue;
		if(++tmp==1) G.add(u,v,T.w[i]),last=u;
		else if(tmp==deg[u]-(u!=1)) G.add(last,v,T.w[i]);
		else G.add(last,++totNode,0),G.add(totNode,v,T.w[i]),last=totNode;
	}
	for(int i=T.fir[u];i;i=T.nex[i])if(T.to[i]^fa) rebuild(T.to[i],u);
}
inline void build(){
	totNode=n;rebuild(1);
	root=0;maxson[0]=_INT_INF;size[0]=n;
	findRoot(1);
	New(rt[0]);divide(root,rt[0],size[1]);
}
inline void update(Node *last,Node *&tree,int u,int k){
	New(tree);
	Node *now=tree;
	for(int id=0;;){
		*now=*last;id=now->id;
		now->size+=k;now->sum+=k*G.getDis(u,id);
		if(newFa[id]) now->sumfa+=k*G.getDis(u,newFa[id]);
		if(id==u) return;
		last=last->son[sonId[u][deep[id]]];
		New(now->son[sonId[u][deep[id]]]);now=now->son[sonId[u][deep[id]]];
	}
}
inline long long ask(Node *l,Node *r,int u){
	long long ans=0;
	Node *nexL,*nexR;
	for(int i=0;ison[sonId[u][i]];nexR=r->son[sonId[u][i]];
		ans+=(r->size-nexR->size-(l->size-nexL->size))*G.getDis(u,r->id)+(r->sum-nexR->sumfa-(l->sum-nexL->sumfa));
	}
	return ans+r->sum-l->sum;
}
int main(){
	n=read();int q=read();
	static int p[N];
	for(int i=1;i<=n;i++) p[i]=read();
	for(int u,v,i=1;i


						
							

						
							
							
			题解-codeforces图论-树分治

CF757G Can Bash Save the Day?

相关

标签