今天开始了学习新算法的艰辛旅程~~~

第一个任务是倍增，本来打算一天完成的，结果完不成……

首先上论文：2005 朱晨光《浅析倍增思想在信息学竞赛中的应用》。

然后是个人理解：

倍增，就是成倍增长，经过我的研究发现，使用倍增算法的题目一般有如下特征：

1.要维护的状态之间呈链状。LCA什么就是例子，因为一个点的所有祖先是在一条链上的。这是具体的链，还有抽象链，见例题二。

2.维护的信息满足结合律以及区间加法（口胡），这个是显然的。

接下来就是题目了。

Prob.01——POJ 1986

这是模版题。这道题要求树上两点之间距离，显然满足倍增的条件，于是在倍增LCA的同时维护一下到祖先的距离，搞搞即可。

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

const int Maxn=40000+19;
struct Edge {int y,z,nxt;} E[Maxn<<1];
int n,m,Q,x,y,z,cnt;
int Last[Maxn],Deep[Maxn],Fa[Maxn][21],Dis[Maxn][21];
char s[5];

inline void AddE(int x,int y,int z) {E[cnt]=(Edge){y,z,Last[x]};Last[x]=cnt++;}
inline void DFS(int x,int D)
{
	Deep[x]=D;
	for (int i=Last[x];i^-1;i=E[i].nxt)
		if (E[i].y^Fa[x][0]) Fa[E[i].y][0]=x,Dis[E[i].y][0]=E[i].z,DFS(E[i].y,D+1);
}
inline int Query(int x,int y)
{
	if (x==y) return 0;
	if (Deep[x]<Deep[y]) swap(x,y);
	int Ans=0;
	for (int i=20;i>=0;i--)
		if (Deep[Fa[x][i]]>Deep[y]) Ans+=Dis[x][i],x=Fa[x][i];
	if (Deep[x]^Deep[y]) Ans+=Dis[x][0],x=Fa[x][0];
	if (x==y) return Ans;
	for (int i=20;i>=0;i--)
		if (Fa[x][i]^Fa[y][i]) Ans+=Dis[x][i]+Dis[y][i],x=Fa[x][i],y=Fa[y][i];
	return Ans+Dis[x][0]+Dis[y][0];
}

int main()
{
	memset(Last,-1,sizeof(Last));
	scanf("%d%d",&n,&m);
	for (int i=0;i<m;i++) scanf("%d%d%d%s",&x,&y,&z,s),AddE(x,y,z),AddE(y,x,z);
	DFS(1,0);
	scanf("%d",&Q);
	for (x=1;x<=20;x++)
		for (int i=1;i<=n;i++) 
		{
			Dis[i][x]=Dis[i][x-1]+Dis[Fa[i][x-1]][x-1];
			Fa[i][x]=Fa[Fa[i][x-1]][x-1];
		}
	while (Q--)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",Query(x,y));
	}
}

Prob.02——HDU 4343

这其实也是一道水题吧。但是我被坑了一晚上……究其原因竟然是没看见多组数据……真是悲伤……

这题的话，就是上面说的“抽象的链”。我们可以对于每条线段维护左边不与它相交的最靠右线段编号，然后把这个信息倍增加速。查询的时候先二分出询问区间内最靠右线段，然后倍增往左扫描即可。

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

const int Maxn=100000+19;
struct seg {int L,R;} A[Maxn],B[Maxn];
int n,_n,m,qL,qR,R[Maxn],pre[Maxn][21];

inline int cmp1(seg a,seg b) {return a.L<b.L||a.L==b.L&&a.R>b.R;}
inline int cmp2(seg a,seg b) {return a.R<b.R||a.R==b.R&&a.L<b.L;}

int main()
{
	while (~scanf("%d%d",&_n,&m))
	{
		n=0;
		memset(pre,0,sizeof(pre));
		for (int i=1;i<=_n;i++) scanf("%d%d",&A[i].L,&A[i].R);
		sort(A+1,A+_n+1,cmp1);
		for (int i=1;i<=_n;i++)
		{
			int Flag=1;
			for (int j=i+1;j<=_n;j++)
			{
				if (A[i].L<=A[j].L&&A[j].R<=A[i].R) {Flag=0;break;}
				if (A[i].R<A[j].L) break;
			}
			if (Flag) B[++n]=A[i];
		}
		sort(B+1,B+n+1,cmp2);
		for (int i=1;i<=n;i++) R[i]=B[i].R;
		for (int i=1;i<=n;i++)
			for (int j=i-1;j;j--)
				if (B[j].R<=B[i].L) {pre[i][0]=j;break;}
		for (int x=1;x<=20;x++)
			for (int i=1;i<=n;i++) pre[i][x]=pre[pre[i][x-1]][x-1];
		B[0].L=-1;
		while (m--)
		{
			scanf("%d%d",&qL,&qR);
			int x=lower_bound(R+1,R+n+1,qR+1)-R-1,Ans=0;
			if (x&&B[x].L>=qL)
			{
				for (int i=20;i>=0;i--)
					if (B[pre[x][i]].L>=qL) x=pre[x][i],Ans+=(1<<i);
				printf("%d\n",Ans+1);
			} else printf("0\n");
		}
	}
}