倍增
给定一个数列,每个位置有一条出边,可以到达自己右边的某一个位置,
每次给定一个位置
一步一步模拟:时间复杂度
加速!我们希望一次能多走几步,怎么做呢?
根号
设数组
我们额外设置一个数组
每次询问的时候,令
这样的复杂度是多少呢?
预处理的时间要花
我们不妨假设
根据基本不等式:
在
具体地,这种方法是预处理和单次查询复杂度是
空间复杂度
for(int i=1;i<=m;++i)
{
int p,k;
cin>>p>>k;
int t=k/cnt,r=k%cnt;
while(t--) p=g[p];
while(r--) p=f[p];
cout<<p<<'\n';
}
2
3
4
5
6
7
8
9
倍增
之前的方法还是不够灵性,一次最多走
考虑到任意一个数字都可以被二进制分解,从这个角度入手。
预处理
这个很好预处理,
然后每次询问,将
预处理和单次查询复杂度是
空间复杂度
for(int t=1;t<=20;++t)
for(int i=1;i<=n;++i) f[i][t]=f[f[i][t-1]][t-1];
for(int i=1;i<=m;++i)
{
int p,k;
cin>>p>>k;
for(int t=20;t>=0;--t)
{
if((k>>t)&1) p=f[p][t];
}
cout<<p<<'\n';
}
2
3
4
5
6
7
8
9
10
11
12
快速幂
求给定
倍增优化:
将指数
所以
int x,n;cin>>x>>n;
pw[0]=x;
for(int i=1;i<=30;++i) pw[i]=pw[i-1]*pw[i-1]%mod;
int ret=1;
for(int k=0;k<=30;++k) if((x>>k)&1)//x的这一位是1
{
ret=ret*pw[k]%mod;
}
2
3
4
5
6
7
8
可以换一种写法,不用额外开数组
int fast(int x,int k)//求x的k次方
{
int ret=1;
while(k)
{
if(k&1) ret=ret*x%mod;//k的最后一位是1
x=x*x%mod;//x倍增
k>>=1;//把最后一位去掉
}
return ret;
}
2
3
4
5
6
7
8
9
10
11
可重复信息静态区间查询(ST表)
对于可重复信息静态区间查询问题,可以使用倍增的方法进行优化:
对于一个数列,每次询问一段子区间中的最大值是多少?
我们可以仿照上面,预处理出
f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
然后当我们询问到一个区间时,假设区间是
区间长度是
设
即
因为最大值是可以重复的元素(很明显两个查询区间之间有交集),且不会对数列进行任何修改,所以可以用这种方式。
预处理和单次查询复杂度是
可重复信息都可以用
不可重复元素如区间和,区间乘积等,不能用
启发式合并
给
1.把第
2.查询所有和第
是不是很难?不知道怎么合并?
其实很简单,暴力合并!
每次合并两种颜色的时候,我们把数量较少的那种颜色加到数量较多的那种颜色里(一个一个元素加入)。
假设两种颜色元素个数是
这样我们花费的时间是
合并之后,颜色元素个数
说明每次合并会让所属的颜色元素个数翻倍。
那么对于任意一个元素,它在合并的时候作为数量较少的那一组的次数不超过
所以被计算不超过
询问次数很少,直接暴力。
核心思想:在总数固定为
vector<vector<int> > col(n+1);//每种颜色现在里面有哪些元素
vector<int> id(n+1);
for(int i=1;i<=n;++i) id[i]=i;//第i种颜色现在变成了哪种颜色
for(int i=1;i<=n;++i)
{
int x;cin>>x;
col[i].emplace_back(x);
}
for(int i=1;i<=n;++i)
{
//合并
int x,y;
cin>>x>>y
if(col[id[x]].size()>col[id[y]].size()) swap(x,y);//让x是个数少的那个颜色
for(int a:col[id[x]]) col[id[y]].emplace_back(a);//把x里的元素全放y里
id[x]=id[y];//把颜色x改成颜色y的颜色
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
练习题
Analysis of Pathes in Functional Graph