初探树链剖分3

SDOI2014 旅行

动态线段树．

题目

题目链接　

调试心得

稳定心态，一定能搞对的　：｜

代码

//very happy 
//get ac :)
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

// notice !!!
// 初始化 maxv 不同的题目,可能会有所变化
// 多组数据时,记得初始化cnt=0 
const int maxv=1e5+10;
struct Edge{ int to,nxt; }edge[maxv*2]; int head[maxv],tot=0;
void addedge(int from,int to){ edge[tot].to=to; edge[tot].nxt=head[from]; head[from]=tot++; }
int cnt,f[maxv],d[maxv],sz[maxv],son[maxv],rk[maxv],top[maxv],pos[maxv];
// get f d sz  dfs1(root,0,1);
int dfs1(int u,int fa,int depth){  // 当前节点、父亲节点、层次深度  dfs1(root,0,1)
	f[u]=fa,d[u]=depth,sz[u]=1;
	int maxson=-1; for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].to; if(v==fa) continue;
		sz[u]+=dfs1(v,u,depth+1); if(sz[v]>maxson){ maxson=sz[v]; son[u]=v; } } return sz[u]; }
		// get rk top pos   cnt=0; dfs2(root,root);
		void dfs2(int u,int t) {// 当前节点，重链顶端
			top[u]=t; pos[u]=++cnt; //标记dfs序列
			rk[cnt]=u;   //序号cnt对应节点u
			if(!son[u]) return; dfs2(son[u],t); 
			/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
			for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].to; if(v!=son[u] && v!=f[u]) dfs2(v,v); } 
		}

const int N=1e5+10;
//动态线段树的结点个数q*log N
const int maxTree=N<<4;

int rt[N],num=0;
struct Tree{
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define mx(x) tree[x].mx
	#define sum(x) tree[x].sum
	int ls,rs,mx,sum;
}tree[maxTree];

void pushup(int o){
	sum(o)=sum(ls(o))+sum(rs(o));
	mx(o)=max(mx(ls(o)),mx(rs(o)));
	return ;
}

void insert(int p,int val,int l,int r,int &o){
	if(!o) o=++num;
	if(l==r){
		sum(o)=mx(o)=val;
		return;
	}
	int m=l+r>>1;
	if(p<=m)  insert(p,val,l,m,ls(o));
	else insert(p,val,m+1,r,rs(o));
	pushup(o);
	return;
}

void remove(int p,int l,int r,int &o){
	if(!o) return;
	if(l==r){
		sum(o)=mx(o)=0;
		return;
	}
	int m=l+r>>1;
	if(p<=m) remove(p,l,m,ls(o));
	else remove(p,m+1,r,rs(o));
	pushup(o);
	return;
}

int getsum(int ql,int qr,int l,int r,int o){
	if(ql<=l && r<=qr) return sum(o);
	int m=l+r>>1,ans=0;
	if(ql<=m)	ans+=getsum(ql,qr,l,m,ls(o));
	if(qr>m)	ans+=getsum(ql,qr,m+1,r,rs(o));
	return ans;
}
int getmax(int ql,int qr,int l,int r,int o){
	if(ql<=l&&qr>=r)	return mx(o);
	int mid=l+r>>1,ans=0;
	if(ql<=mid) ans=max(ans,getmax(ql,qr,l,mid,ls(o)));
	if(qr>mid)	ans=max(ans,getmax(ql,qr,mid+1,r,rs(o)));
	return ans;
}

int n,q;
int val[maxv],c[maxv];

void change_color(int x,int y){
	remove(pos[x],1,n,rt[c[x]]);
	c[x]=y;
	insert(pos[x],val[x],1,n,rt[y]);
	return;
}

void change_weight(int x,int y){
	val[x]=y;
	insert(pos[x],y,1,n,rt[c[x]]);
	return;
}

int query_sum(int x,int y){
	int ans=0,col=c[x];
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])	swap(x,y);
	//	ans=max(ans,getmax(1,n,rt[col],id[x],id[y]));
		ans+=getsum(pos[top[x]],pos[x],1,n,rt[col]);
		x=f[top[x]];
	}
	if(d[x]>d[y])	swap(x,y);
	ans+=getsum(pos[x],pos[y],1,n,rt[col]);
	return ans;
}

int query_max(int x,int y){
	int ans=0,col=c[x];
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])	swap(x,y);
		ans=max(ans,getmax(pos[top[x]],pos[x],1,n,rt[col]));
		x=f[top[x]];
	}
	if(d[x]>d[y])	swap(x,y);
	ans=max(ans,getmax(pos[x],pos[y],1,n,rt[col]));
	return ans;
}

int main(){
	scanf("%d%d",&n,&q); inc(i,1,n) scanf("%d%d",val+i,c+i);
	tot=0;mst(head,-1);
	inc(i,2,n){ int x,y;scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}
	cnt=0;dfs1(1,0,1);dfs2(1,1);
	inc(i,1,n) insert(pos[i],val[i],1,n,rt[c[i]]);
	while(q--){ char ch[10];scanf(" %s",ch);
		int x,y;scanf("%d%d",&x,&y);
		char op=ch[1];
		switch(op){
			case 'C': change_color(x,y);break;
			case 'W': change_weight(x,y);break;
			case 'S': printf("%d\n",query_sum(x,y));break;
			case 'M': printf("%d\n",query_max(x,y));break;
		}
	}
	return 0;
}

带内存回收的代码

2020.8.44 UDP
上述的代码，删除的节点的空间是直接放弃的
但是其实是可以回收利用的：）

参考了如下资料
https://www.luogu.com.cn/blog/ix-35/solution-p6012

//very happy 
//get ac :)
//
#include <bits/stdc++.h>
using namespace std;
#define inc(i,a,b) for(int i=a;i<=b;i++)
#define dec(i,a,b) for(int i=a;i>=b;i--)
#define ll long long 
#define mst(a,b) memset(a,b,sizeof a)
#define pb push_back
inline int read(){
	char ch=getchar();int f=1,x=0;
	while(!isdigit(ch)) { if(ch=='-') f=-1;ch=getchar();}
	while(isdigit(ch)){ x=x*10+ch-'0';ch=getchar();}
	return f*x;
}

// notice !!!
// 初始化 maxv 不同的题目,可能会有所变化
// 多组数据时,记得初始化cnt=0 
const int maxv=1e5+10;
struct Edge{ int to,nxt; }edge[maxv*2]; int head[maxv],tot=0;
void addedge(int from,int to){ edge[tot].to=to; edge[tot].nxt=head[from]; head[from]=tot++; }
int cnt,f[maxv],d[maxv],sz[maxv],son[maxv],rk[maxv],top[maxv],pos[maxv];
// get f d sz  dfs1(root,0,1);
int dfs1(int u,int fa,int depth){  // 当前节点、父亲节点、层次深度  dfs1(root,0,1)
	f[u]=fa,d[u]=depth,sz[u]=1;
	int maxson=-1; for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].to; if(v==fa) continue;
		sz[u]+=dfs1(v,u,depth+1); if(sz[v]>maxson){ maxson=sz[v]; son[u]=v; } } return sz[u]; }
		// get rk top pos   cnt=0; dfs2(root,root);
		void dfs2(int u,int t) {// 当前节点，重链顶端
			top[u]=t; pos[u]=++cnt; //标记dfs序列
			rk[cnt]=u;   //序号cnt对应节点u
			if(!son[u]) return; dfs2(son[u],t); 
			/*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续， 一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
			for(int i=head[u];~i;i=edge[i].nxt){ int v=edge[i].to; if(v!=son[u] && v!=f[u]) dfs2(v,v); } 
		}

const int N=1e5+10;
//动态线段树的结点个数q*log N
const int maxTree=N<<4;

int rt[N],num=0;

struct Tree{
	#define ls(x) tree[x].ls
	#define rs(x) tree[x].rs
	#define mx(x) tree[x].mx
	#define sum(x) tree[x].sum
	int ls,rs,mx,sum;
}tree[maxTree];

void pushup(int o){
	sum(o)=sum(ls(o))+sum(rs(o));
	mx(o)=max(mx(ls(o)),mx(rs(o)));
	return ;
}

//带内存回收的版本
//如果多组数据记得初始化ins=0
int mem[maxv];
int ins;
int newnode(){
	///return ++num;

	return ins?mem[ins--]:++num;
}

void delnode(int &p){
	mem[++ins]=p;
//	cout<<"oh "<<ins<<endl;
	ls(p)=rs(p)=mx(p)=sum(p)=0;
	p=0;
}



void insert(int p,int val,int l,int r,int &o){
	if(!o) o=newnode();
	if(l==r){
		sum(o)=mx(o)=val;
		return;
	}
	int m=l+r>>1;
	if(p<=m)  insert(p,val,l,m,ls(o));
	else insert(p,val,m+1,r,rs(o));
	pushup(o);
	return;
}

void remove(int p,int l,int r,int &o){
	if(!o) return;
	if(l==r){
		delnode(o);
		o=0;
		return;
	}
	int m=l+r>>1;
	if(p<=m) remove(p,l,m,ls(o));
	else remove(p,m+1,r,rs(o));
	pushup(o);
	return;
}

int getsum(int ql,int qr,int l,int r,int o){
	if(ql<=l && r<=qr) return sum(o);
	int m=l+r>>1,ans=0;
	if(ql<=m)	ans+=getsum(ql,qr,l,m,ls(o));
	if(qr>m)	ans+=getsum(ql,qr,m+1,r,rs(o));
	return ans;
}
int getmax(int ql,int qr,int l,int r,int o){
	if(ql<=l&&qr>=r)	return mx(o);
	int mid=l+r>>1,ans=0;
	if(ql<=mid) ans=max(ans,getmax(ql,qr,l,mid,ls(o)));
	if(qr>mid)	ans=max(ans,getmax(ql,qr,mid+1,r,rs(o)));
	return ans;
}

int n,q;
int val[maxv],c[maxv];

void change_color(int x,int y){
	remove(pos[x],1,n,rt[c[x]]);
	c[x]=y;
	insert(pos[x],val[x],1,n,rt[y]);
	return;
}

void change_weight(int x,int y){
	val[x]=y;
	insert(pos[x],y,1,n,rt[c[x]]);
	return;
}

int query_sum(int x,int y){
	int ans=0,col=c[x];
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])	swap(x,y);
	//	ans=max(ans,getmax(1,n,rt[col],id[x],id[y]));
		ans+=getsum(pos[top[x]],pos[x],1,n,rt[col]);
		x=f[top[x]];
	}
	if(d[x]>d[y])	swap(x,y);
	ans+=getsum(pos[x],pos[y],1,n,rt[col]);
	return ans;
}

int query_max(int x,int y){
	int ans=0,col=c[x];
	while(top[x]!=top[y]){
		if(d[top[x]]<d[top[y]])	swap(x,y);
		ans=max(ans,getmax(pos[top[x]],pos[x],1,n,rt[col]));
		x=f[top[x]];
	}
	if(d[x]>d[y])	swap(x,y);
	ans=max(ans,getmax(pos[x],pos[y],1,n,rt[col]));
	return ans;
}

int main(){
	scanf("%d%d",&n,&q); inc(i,1,n) scanf("%d%d",val+i,c+i);
	tot=0;mst(head,-1);
	inc(i,2,n){ int x,y;scanf("%d%d",&x,&y);addedge(x,y);addedge(y,x);}
	cnt=0;dfs1(1,0,1);dfs2(1,1);
	inc(i,1,n) insert(pos[i],val[i],1,n,rt[c[i]]);
	while(q--){ char ch[10];scanf(" %s",ch);
		int x,y;scanf("%d%d",&x,&y);
		char op=ch[1];
		switch(op){
			case 'C': change_color(x,y);break;
			case 'W': change_weight(x,y);break;
			case 'S': printf("%d\n",query_sum(x,y));break;
			case 'M': printf("%d\n",query_max(x,y));break;
		}
	}
	return 0;
}

参考资料

https://loj.ac/submission/906239

https://www.cnblogs.com/fusiwei/p/12628596.html

可能的应用
https://www.dazhuanlan.com/2019/12/12/5df12764defa5/

线段树合并
https://blog.csdn.net/weixin_44178736/article/details/100097996