【BZOJ1036】[ZJOI2008] 树的统计Count（一道可怕的模板题：树剖+线段树）

题解

这真的只是一道模板题：一个树链剖分套上一个线段树（令我窒息的组合）。
既然是模板题，那就直接上代码吧。
代码

#include<bits/stdc++.h>

#define N 30000

using namespace std;

int n,ee=0,tot=0,a[N+5],lnk[N+5],fa[N+5],Size[N+5],Depth[N+5],Wson[N+5],Top[N+5],Pos[N+5],Num[N+5];

int Sum[N<<2],Max[N<<2];

struct edge

{

	int to,nxt;

}e[2*N+5];

inline char tc()

{

	static char ff[100000],*A=ff,*B=ff;

	return A==B&&(B=(A=ff)+fread(ff,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

	x=0;int f=1;char ch;

	while(!isdigit(ch=tc())) if(ch=='-') f=-1;

	while(x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

	x*=f;

}

inline void write(int x)

{

	if(x<0) putchar('-'),x=-x;

	if(x>9) write(x/10);

	putchar(x%10+'0');

}

inline void read_string(string &st)

{

	st="";char ch;

	while((ch=tc())<'A'||ch>'Z');

	while(st+=ch,(ch=tc())>='A'&&ch<='Z');

}

inline void add(int x,int y)

{

	e[++ee]=(edge){y,lnk[x]},lnk[x]=ee;

}

inline void dfs1(int x)//第一遍DFS，预处理出每个节点的父亲、深度、重儿子以及子树大小

{

	register int i;Size[x]=1;

	for(i=lnk[x];i;i=e[i].nxt)

		if(e[i].to^fa[x]) fa[e[i].to]=x,Depth[e[i].to]=Depth[x]+1,dfs1(e[i].to),Size[x]+=Size[e[i].to],(Size[e[i].to]>Size[Wson[x]]?Wson[x]=e[i].to:0);

}

inline void dfs2(int x,int tp)//第二遍DFS，根据先前预处理出的重儿子，剖分出轻重链

{

	register int i;Top[Num[Pos[x]=++tot]=x]=tp;

	if(Wson[x]) dfs2(Wson[x],tp);

	for(i=lnk[x];i;i=e[i].nxt)

		if(e[i].to!=fa[x]&&e[i].to!=Wson[x]) dfs2(e[i].to,e[i].to);

}

inline void PushUp(int rt)

{

	Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1],Max[rt]=max(Max[rt<<1],Max[rt<<1|1]);

}

inline void Build(int l,int r,int rt)//一个朴素的建树过程

{

	if(l==r)

	{

		Sum[rt]=Max[rt]=a[Num[l]];

		return;

	}

	int mid=l+r>>1;

	Build(l,mid,rt<<1),Build(mid+1,r,rt<<1|1),PushUp(rt);

}

inline void Update(int l,int r,int rt,int x,int v)//单点修改

{

	if(l==r)

	{

		Sum[rt]=Max[rt]=v;

		return;

	}

	int mid=l+r>>1;

	(mid>=x?Update(l,mid,rt<<1,x,v):Update(mid+1,r,rt<<1|1,x,v)),PushUp(rt);

}

inline int Query_Max(int l,int r,int rt,int L,int R)//查询区间最大值

{

	if(L>R) L^=R,R^=L,L^=R;

	if(L<=l&&r<=R) return Max[rt];

	int mid=l+r>>1,res=-1e9;

	if(L<=mid) res=max(res,Query_Max(l,mid,rt<<1,L,R));

	if(R>mid) res=max(res,Query_Max(mid+1,r,rt<<1|1,L,R));

	return res;

}

inline int Query_Sum(int l,int r,int rt,int L,int R)//查询区间和

{

	if(L>R) L^=R,R^=L,L^=R;

	if(L<=l&&r<=R) return Sum[rt];

	int mid=l+r>>1,res=0;

	if(L<=mid) res+=Query_Sum(l,mid,rt<<1,L,R);

	if(R>mid) res+=Query_Sum(mid+1,r,rt<<1|1,L,R);

	return res;

}

inline int Qmax(int s1,int s2)//对数据进行处理，并调用线段树的Query_Max()函数来求出答案

{

	int res=-1e9;

	while(Top[s1]^Top[s2])

	{

		if(Depth[Top[s1]]<Depth[Top[s2]]) s1^=s2,s2^=s1,s1^=s2;

		res=max(res,Query_Max(1,n,1,Pos[Top[s1]],Pos[s1])),s1=fa[Top[s1]];

	}

	if(Depth[s1]<Depth[s2]) s1^=s2,s2^=s1,s1^=s2;

	return max(res,Query_Max(1,n,1,Pos[s1],Pos[s2]));

}

inline int Qsum(int s1,int s2)//对数据进行处理，并调用线段树的Query_Sum()函数来求出答案

{

	int res=0;

	while(Top[s1]^Top[s2])

	{

		if(Depth[Top[s1]]<Depth[Top[s2]]) s1^=s2,s2^=s1,s1^=s2;

		res+=Query_Sum(1,n,1,Pos[Top[s1]],Pos[s1]),s1=fa[Top[s1]];

	}

	if(Depth[s1]<Depth[s2]) s1^=s2,s2^=s1,s1^=s2;

	return res+Query_Sum(1,n,1,Pos[s1],Pos[s2]);

}

int main()

{

	freopen("a.in","r",stdin);

	register int i;int x,y;

	for(read(n),i=1;i<n;++i)

		read(x),read(y),add(x,y),add(y,x);

	for(i=1;i<=n;++i)

		read(a[i]);

	dfs1(1),dfs2(1,1),Build(1,n,1);

	int Q;read(Q);

	while(Q--)

	{

		string st;

		read_string(st),read(x),read(y);

		if(st=="CHANGE") Update(1,n,1,Pos[x],y);

		else if(st=="QMAX") write(Qmax(x,y)),putchar('\n');

		else if(st=="QSUM") write(Qsum(x,y)),putchar('\n');

	}

	return 0;

}
巴特西

【BZOJ1036】[ZJOI2008] 树的统计Count（一道可怕的模板题：树剖+线段树）

题解

代码

最新文章

热门文章
