【T】分治与倍增

分治，分而治之，其中最经典的便是二分

一、二分

一种经典而且非常好用的思想
将原问题对半转换成两个问题，子问题又继续转换成两个问题，许多子问题会很显然对答案没有关系，所以能讲原本O(n)的东西转化为O(logn)
但一般有个条件：单调

（之前讲的快速幂其实也用到的是这类思想）

经典讲法：猜数字

现在有个1-100的数字让你猜，每次会回答你猜的大了还是小了，尽量用最少次数猜出答案
二分实现：每次猜中间的数，然后缩小一般的区间重复操作

#include<bits/stdc++.h>
using namespace std;
int x,a;
int main()
{
	srand(time(0));
	x=rand()%100+1;//x为1-100
	printf("猜1-100的某个数\n");
	while(scanf("%d",&a))
	{
		if(a>x)printf("猜大了\n");
		if(a<x)printf("猜小了\n");
		if(a==x){printf("**对了**\n");return 0;}
	}
}

P2249 【深基13.例1】查找

这个数列是单调不减，所以可以直接用二分来找

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000005],x;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
	for(int i=1;i<=m;i++)
	{
		scanf("%d",&x);
		/*
		int ans=lower_bound(a+1,a+n+1,x)-a;//二分搜，注意-a
		if(x!=a[ans]) printf("-1 ");//没有，输出-1
		虽然可以用这个自带函数，但我们这里学的是思想，二分思想很重要
		*/
		int l=1,r=n,mid;
		while(l<r)
		{
			mid=(l+r)>>1;
			if(x<=a[mid])r=mid;
			else	     l=mid+1;//等号可能要多思考一下,+1也要思考下
		}
		if(a[l]==x)printf("%d ",l);
		else	   printf("-1 ");
	}
}

P1024 [NOIP2001 提高组] 一元三次方程求解

熟悉一下实数版二分，有时判断的时候可能需要一个eps=1e-3用来辅助判断，因为实数精度判断有时可能不太准确

#include<bits/stdc++.h>
using namespace std;
double a,b,c,d;
double f(double x)
{
	return a*x*x*x+b*x*x+c*x+d;
}

int main()
{
	scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
	for(int i=-100;i<100;i++)
	{
		double l=i,r=i+1,mid;
		if(f(l)==0){printf("%.2lf ",l);continue;}
		if(f(l)*f(r)<0)
		{
			while(r-l>=0.001)
			{
				mid=(l+r)/2;
				if(f(mid)*f(l)<=0)r=mid;
				else			  l=mid;
				//printf("[%.2lf,%.2lf](%lf)\n",l,r,f(l));
			}
			printf("%.2lf ",l);
		}
		//l为答案
	}
}

P2678 跳石头

二分答案，再学会check对于mid是否成立
需要想到问题对于答案是个单增的，如果mid成立，则>mid也都成立

三分

一般处理单峰函数，不常用的板子
可以看到三分板子题解全在叫你用一堆什么随机算法，单峰函数也不常见，反而随机算法各种题说不定还能对

二、倍增

分治是把问题分开解决，而倍增是从成倍整合解决

ST表

预处理 $2^0$ 步转移，然后 $2^1- 2^{20}$ 步分别由之前步整合得到

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int bz[N][20],lg[N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&bz[i][0]);
	for(int j=1;j<=18;j++)
		for(int i=1;i<=n;i++)
			if(i+(1<<(j-1))<=n)
	bz[i][j]=max(bz[i][j-1],bz[i+(1<<(j-1))][j-1]);//重点精髓语句
	int l,r;
	while(m--)
	{
		scanf("%d%d",&l,&r);
		int p=log2(r-l+1);
		printf("%d\n",max(bz[l][p],bz[r-(1<<p)+1][p]));
	}
}

练习：P1816 忠诚

树上倍增->LCA最近公共祖先

等会建图啊，树相关啊，再回来看(讲），有空的可以先看看学学

#include<bits/stdc++.h>
using namespace std;
const int N=1000009;
int n,q,x,y,nex[N*2],first[N*2],to[N*2],tot=0;
int f[N][21],dep[N];
void Add(int u,int v) //建邻接表
{
	nex[++tot]=first[u];first[u]=tot;to[tot]=v;
	nex[++tot]=first[v];first[v]=tot;to[tot]=u;
}
void Init(int u,int father) //预处理，father 是 u 的父节点
{
	dep[u]=dep[father]+1;
	for(int i=0;i<=19;i++) //预处理出从某个点跳 2 的 i 次方到达的位置
	f[u][i+1]=f[f[u][i]][i];
	for(int e=first[u];e;e=nex[e]) //枚举每一条与 u 相连的点
	{
		int v=to[e];
		if(v==father) continue; //如果这条连向父节点，就 continue 
		f[v][0]=u; //v 的父亲是 u 
		Init(v,u); //递归
	}
}
int Lca(int x,int y) //找 LCA 
{
	if(dep[x]<dep[y]) swap(x,y); //保证 x 深度更大
	for(int i=20;i>=0;i--) //使它们俩跳至深度相同
	{
		if(dep[f[x][i]]>=dep[y]) x=f[x][i];
		if(x==y) return x; //属于 x、y 在一条链上，y 是 x 和 y 的最近公共祖先
	}
	for(int i=20;i>=0;i--) //在 x 和 y 深度相同的情况下
		if(f[x][i]!=f[y][i]) //目标位置不相等，x 和 y 就往上爬
		{
			x=f[x][i]; //x 往上爬
			y=f[y][i]; //y 往上爬
		}
	return f[x][0]; //最后肯定一起跳到了 lca 的下面一个
}
int dist(int x,int y){return dep[x]+dep[y]-2*dep[Lca(x,y)];} //求距离
int main()
{
	scanf("%d",&n);
	scanf("%d",&q);
	int st;
	scanf("%d",&st);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		Add(x,y);
	}
	Init(st,0); //预处理
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&x,&y);
		printf("%d\n",Lca(x,y));
	}
	return 0;
}