倍增
倍增？二分？递归？递推！
题单
- CodeForces - 359D (-[x]打钩方法)
倍增法
本质：吾以为倍增法本质就是将二分的过程存了下来，二分本来是个递归的过程嘛，倍增法就是将其变成递推了。比如二分可以将其划为两个子问题求解，这两个子问题可以是重复性贡献，也可以是不重复性贡献的，然后再用递推式将其求出来。更详细的理解可以见例题
倍增法本身的复杂度是O(nlogn)的，然后可以O(1)的查询，所以倍增法适用于多次询问的情况，如果只有1次询问的话，就没必要倍增了，直接算就行了。但倍增本身复杂度也不高，O(nlogn)，也可以用来解决1次询问情况，不过就是有些大材小用了。
ST表
模板
1 |
|
ST表-二维RMQ
LCA-最近公共祖先
P3379 【模板】最近公共祖先（LCA）
模板
这个模板注意下dfs里面fa初始化的问题，要么直接设置为常数，要么就改为i<=lg2[d[now]-1],然后再在lca函数的if改成if (fa[x][k] != fa[y][k] && k <= lg2[d[x] - 1])
1 | /*** |
RMQ灵活运用，求区间最常出现数字的数量
Frequent values POJ - 3368
题意：给一个数列n，n是非递减序列，有重复数字。有q次询问，n,q<1e5，每次问在区间[l,r]内最经常出现的数字的数量。
思路：将连续相同的数字看成一个块，预处理出每个块含有的数字的数量，以及块的右坐标。这个预处理出来的值可以封装成结构体减少空间。也可以直接在原数组的基础上，加两个数组num[i]表示i所处块含有的数字数量，pos[i]表示i映射到st表中的坐标。一开始我是用的第一个方法，麻烦了些，看了别人的题解知道第二个方法，确实方便些，直接以空间换时间，反正ACM竞赛嘛。对于每次查询，可以将答案分成三部分，左边残余块，中间连续一整块，用RMQ处理，右边残余块，取三者最大值即可。
踩坑：这个方法不适用于所有情况，就要分类讨论，不要怕麻烦，如果这个方法不适用于所有情况，那就得分类讨论，不然偷懒的话，找BUG的时间你知道的，都够再写道题了。比如这里很明显，不是每次都有中间区间，如果每次都按有中间区间来算，就错了。可能l,r在一个块内，没有中间区间，l,r在两个相邻的块，也没有中间区间，当l,r中间隔一个块时，才有中间区间。然后这里又设计左右坐标的加减，没有一个统一的方法处理，很明显需要分类讨论。
LCA灵活运用，求树上两点间距离
How far away ？ HDU - 2586
题意：给你一个无向树，求任意两点间距离，多次询问。
思路：统一以某个点为根节点，记录每个点到根节点的距离，两点之间距离就等于lca到两点的距离之和。
区间覆盖，倍增法好题
Minimal Segment Cover
题意：给你n个区间，有m次询问，n,m<2e5,每次询问区间A最少需要几个区间就能被完全覆盖，若不存在则输出-1。
思路：这道题先要预处理一下，就很好做了，先预处理出以每个点为起点，只用一个区间能到达的最右端点。然后我们就会想知道，每个起点用2个区间，3个区间，n个区间向右最远能到哪。因为n最大为2e5，所以最多可以用2e5个区间，这个时候就要用上倍增的思想了，用dp[i][j]表示起点i用2^j个区间所能到达的最右端点，则dp[i][j]=dp[ dp[i][j-1] ][j-1]。
代码有些细节要注意：
1 | for(ll i=1,l,r;i<=n;i++){ |
树上与a，b距离相等的点有多少个
A and B and Lecture Rooms
题意：如题，有多次询问
思路：size[i]存下子树i的规模，求得lca点下层的两个点a,b，答案就为
size[lca]-size[a]-size[b]，答案具体的加减法不是这样，这只是表达个大概意思。
a中一区间是否存在子序列为p的一个排列-倍增好题
Lynyrd Skynyrd
题意：a,p,q<2e5，a是数列a长度，p是排列p长度，q是询问次数。子序列是指a的按相对顺序排列的序列，不是子串。p的一个排列是指循环排列。
思路：懒得写了，看这篇吧，注意其中的倍增思想
题解
解释一下题解中第二个3，其前缀是1，1在a中是第二个位置。这样做是因为我们要贪心，找a中距离Ai最近的那个数组成排列。
树中a的k级子孙有多少个-二分好题
Blood Cousins
当然也可以树上启发式合并来做，但我不会，下次再学
思路：对于求某个点的k级子孙，可以把树的每个结点按dfs序编号，记录每种深度含有的编号，记录每个结点，其子树的头个编号L[i]和最后一个编号R[i]。那么求其k级子孙，将其对应深度d，那么在所有深度为d的结点中，因为其结点编号按升序排序，所以可以二分的找到L[i]和R[i]的位置，两个位置之间的数量就为其k级子孙个数。
3⭐ST表-GCD-二分-线段树慢
Pair of Numbers
题意：给一个长度为3e5的数列，记区间a为[l,r]，在区间a内存在一个数，使得所有区间a内的数都能整除它，求最长的区间a，若存在多个，则按左端点顺序从低到高输出。
思路：
1.朴素简单做法
区间a内所有数都能整除它，那它一定是这个区间内的最小数。对于区间内一个数a1，我们求得以其为最小值的整除区间的最大长度，[l,r]，下次枚举，我们可以直接从a[r+1]开始枚举，因为对于a1到ar之间的数，他们的左端点最多为a1，右端点最多为ar，区间长度不会比a1的长。
2.二分-ST表做法
一开始想用线段树做，但是没考虑gcd的复杂度也是logn，然后就超时了，呜呜呜。用ST表就不会，因为ST表把每次GCD的值保存了下来，这里可以仔细考虑下线段树和ST表的复杂度差别。然后我一开始用ST表写，是没想到二分长度l的，我是想着一边建表，一边update，但是这样子模拟很麻烦，不好写代码，虽然复杂度肯定比较低，但是没二分来的逻辑清晰，代码好写，况且二分的复杂度是够的！！！二分的具体做法，在这里我们建两个ST表，一个最小值的，一个gcd的，如果gcd==minn，就是可以的，然后二分长度，对于每个长度，我们枚举n个数。所以复杂度是O(n*logn)的。
倍增，贪心，超时？
题目大意：给出一棵初始时只有一个点的树，每个点都有两个值:ai,ci,分别代表黄金的个数和单价。需要执行m<3e5次操作，每次操作分为两种类型：
1 pi ai ci 添加一个新点,pi为其父节点,保证ci>c(pi)
2 v w :需要从点v到根节点的这条路径上采集w个单位的黄金，问如何采集才能使得总花费最少
注意对于每次操作2是会叠加的,即采集的黄金会拿走掉，下次能拿的黄金就变少了，且强制在线输出。
点击查看思路
注意到ci>c(pi),就很简单了，就贪心，每次从根节点开始拿即可，关键是找到离根节点最近的非空结点。但是我当时想的是一个一个拿会不会超时，如果真要卡的话，确实能卡掉，但是，现在一想，这样的数据造不出来！！！再者，考试的时候也可以试一试嘛，万一数据水了呢？超时就再说嘛，试了还有机会，不试就肯定没机会那么直接简单倍增+贪心就可以了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
* @Author: Marhoosh
* @Date: 2021-09-04 21:45:32
* @Last Modified by: Marhoosh
* @Last Modified time: 2021-09-17 20:13:34
*/
using namespace std;
typedef long long ll;
const ll maxn=3e5+11;
ll fa[maxn][22],a[maxn],c[maxn];
ll found(ll x){
for(ll i=20;i>=0;i--){
if(a[fa[x][i]]) x=fa[x][i];
}
return x;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll q;cin>>q>>a[0]>>c[0];
for(ll i=1,op,vi,wi;i<=q;i++){
cin>>op;
if(op==1){
cin>>fa[i][0]>>a[i]>>c[i];
for(ll j=1;j<=20;j++) fa[i][j]=fa[fa[i][j-1]][j-1];
}
else{
cin>>vi>>wi;ll ans1=0,ans2=0;
while(a[vi]&&wi){
ll fv=found(vi);
ll minn=min(wi,a[fv]);
ans1+=minn;a[fv]-=minn;wi-=minn;
ans2+=minn*c[fv];
}
cout<<ans1<<" "<<ans2<<endl;
}
}
return 0;
}
倍增-思维好题
一开始自己想的是有多少个循环节，先用dfs遍历出有多少个循环节，然后再数出所有循环节内个数，即为可放机器人个数。然后再枚举每个为0的点，看他对应循环节的哪个位置。。。很明显，这么写就纯模拟，而且很复杂。然后因为我一直是按一个格子来思考，无论怎么想，都不会出正解。因为题目很明显表示出来格子之间是有影响的，不是相互独立的。如果我能够按两个格子一起走来思考，应该就不难想出来了。有些东西没考虑到，是不可能想出来的，比如这题不考虑其他格子的影响
1 |
|