[笔记] 倍增相关
凸包凸壳相关 (Updating)

[笔记] 树链剖分

RXDoi posted @ 2014年8月22日 16:16 in 笔记 , 339 阅读

啦啦啦~上午看书学了学树剖,其实以前也看过一次。

感觉基本的原理还是挺简单的。

大致思路就是:把一棵树划分成若干条重路径,重路径之间用轻边连接。某条重路径上的信息用数据结构维护,轻边的信息暴力,然后复杂度O(log^2 n)。

每个节点连向Size最大的子节点的那条边为重边。其余为轻边。

查询的时候类似倍增LCA,每次翻到当前重路径以外的第一个点即可。


BZOJ 1036 树的统计

这道题要维护链上修改,链上Max,Sum,用线段树维护就行了。模版题。

需要注意的是:虽然重路径的数目是O(log n),但是数组不能只开这么大,我后来开成了O(n)。因为那些孤零零的一个节点也要算成重路径的……

#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;

const int M=30000+19,oo=(1<<30)-1;
typedef int one[M],Log[M],Seg[M<<2];
struct Edge {int x,y,nxt;} E[M*2];
int n,Ecnt,cnt,t,v,Q,_sum,_max,qL,qR,x,y;
one SL,Last,Fa,size,Deep,rank,Bel;
Log top;
Seg Lsn,Rsn,Max,Sum;
char s[10];

int c,f;
inline void Read(int &x)
{
	while (!isdigit(c=getchar())&&c!='-');
	if (c=='-') x=0,f=1;else x=c-'0',f=0;
	while (isdigit(c=getchar())) x=x*10+c-'0';
	if (f) x=-x;
}

inline void Add_E(int x,int y)
{
	E[Ecnt]=(Edge){x,y,Last[x]};Last[x]=Ecnt++;
	E[Ecnt]=(Edge){y,x,Last[y]};Last[y]=Ecnt++;
}
inline void DFS(int x)
{
	int Max=0,Idx;
	size[x]=1;
	for (int i=Last[x];i^-1;i=E[i].nxt)
		if (E[i].y^Fa[x])
		{
			int y=E[i].y;Fa[y]=x;Deep[y]=Deep[x]+1;
			DFS(y);
			size[x]+=size[y];
			if (size[y]>Max) Max=size[y],Idx=y;
		}
	if (size[x]==1)
	{
		top[Bel[x]=++cnt]=x;
		rank[x]=1;
	}
	for (int i=Last[x];i^-1;i=E[i].nxt)
		if (E[i].y^Fa[x]&&E[i].y==Idx)
		{
			int y=E[i].y;
			top[Bel[x]=Bel[y]]=x;
			rank[x]=rank[y]+1;
		}
}
inline void Update(int &x,int L,int R)
{
	if (!x) x=++cnt;
	if (L==R) {Max[x]=Sum[x]=v;return;}
	int Mid=(L+R)>>1;
	if (t<=Mid) Update(Lsn[x],L,Mid);else Update(Rsn[x],Mid+1,R);
	Max[x]=max(Max[Lsn[x]],Max[Rsn[x]]);
	Sum[x]=Sum[Lsn[x]]+Sum[Rsn[x]];
}
inline void Count(int x,int L,int R)
{
	if (!x) return;
	if (qL<=L&&R<=qR) {_sum+=Sum[x];_max=max(_max,Max[x]);return;}
	int Mid=(L+R)>>1;
	if (qL<=Mid) Count(Lsn[x],L,Mid);
	if (qR>Mid) Count(Rsn[x],Mid+1,R);
}
inline void Query()
{
	int a=Bel[x],b=Bel[y];
	_sum=0;_max=-oo;
	while (a!=b)
	{
		if (Deep[top[a]]<Deep[top[b]]) swap(x,y),swap(a,b);
		qL=rank[x];qR=rank[top[a]];
		Count(a,1,qR);
		x=Fa[top[a]];a=Bel[x];
	}
	if (rank[x]>rank[y]) swap(x,y);
	qL=rank[x];qR=rank[y];
	Count(a,1,rank[top[a]]);
}

int main()
{
	memset(Last,-1,sizeof(Last));
	scanf("%d",&n);
	for (int i=1;i<n;i++) Read(x),Read(y),Add_E(x,y);
	DFS(1);
	for (int i=1;i<=n;i++) Read(v),t=rank[i],Update(Bel[i],1,rank[top[Bel[i]]]);
	scanf("%d",&Q);
	while (Q--)
	{
		scanf("%s",s);
		if (s[0]=='C') Read(x),Read(v),t=rank[x],Update(Bel[x],1,rank[top[Bel[x]]]);
		if (s[0]=='Q') Read(x),Read(y),Query(),printf("%d\n",s[1]=='M'?_max:_sum);
	}
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter