倍增+DP

最近做的3题倍增+dp题，大致思想都是预处理出$dp[i][j]$,即$i$位置跳$2^j$步能到达的最远距离，和求$LCA$差不多。

Codeforce 1175 EMinimal Segment Cover

$dp[i][j]$表示$i$位置往右选择$2^j$个区间能到达的最远位置，根据输入处理出$dp[i][0]$，$dp[i][0] = max(dp[i][0], max(i,dp[i - 1][0]))$,然后预处理出$dp$数组。询问的时候贪心即可。

#include<bits/stdc++.h>
using namespace std;
const int mx = 20;
const int N = 5e5 + 10;
int dp[N][mx];
int n, m,mxdis;
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		dp[l][0] = max(dp[l][0], r);
		mxdis = max(mxdis, r);
	}
	for (int i = 1; i <= mxdis; i++)
	{
		dp[i][0] = max(dp[i][0], max(i,dp[i - 1][0]));
	}
	for (int j = 1; j < mx; j++)
	{
		for (int i = 0; i <= mxdis; i++)
		{
			dp[i][j] = dp[dp[i][j - 1]][j - 1];
		}
	}
	while (m--)
	{
		int l, r;
		scanf("%d%d", &l, &r);
		int ans = 0;
		for (int j = mx - 1; j >= 0; j--)
		{
			if (dp[l][j] < r){
				ans += (1 << j);
				l = dp[l][j];
			}
		}
		l = dp[l][0];
		if (dp[l][0] < r){
			puts("-1");
			continue;
		}
		printf("%d\n", ans + 1);
	}
	return 0;
}

题目链接： 牛客 区间的连续段

现利用前缀和二分得到dp[i][0]，即i往右跳一步能到达的最远的位置r，我们使用upper_bound,注意这个位置r是不包含在我们一步所能到达的区间内的，即我们一步只能得到区间$\left [ dp[i][0],r \right )$ . 这个r代表下一步的起点，仔细想想很巧妙。

注意$dp[n+1][i](i \in [1 ,n])$要设为$n+1$.因为处理$dp[i][0]$的时候可能返回$n+1$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int n, m, k;
ll a[N];
int dp[N][25];
int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
        a[i] += a[i - 1];
    for (int i = 0; i <= 20; i++)
        dp[n+1][i] = n + 1;
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = upper_bound(a + 1, a + n + 1, a[i - 1] + k) - a;
        //cout << dp[i][0] << endl;
    }
    for (int j = 1; j <= 20; j++)
        for (int i = 1; i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
    while (m--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        int res = 0;
        for (int j = 20; j >= 0; j--)
            if (dp[l][j] <= r) res += (1 << j), l = dp[l][j];
        if (dp[l][0] <= r) puts("Chtholly");
        else printf("%d\n", res + 1);
    }
    return 0;
}

题目链接： Codeforce 932 D

树上倍增

$fat[i][j]$ 表示$i$节点往上走的第$2^j$个父亲，注意这里的父节点不是普通的父节点，而是满足条件的父节，即父节点的权值比子节点大,如果没有点权值比当前节点大，那父节点就是0. $sum[i][j]$表示i往上走$2^j$个节点得到的权值和，$sum[1][i](i \in [1 ,n])$ 要设为$inf$，因为$1$节点就不能往上走了，设为$0$的话$1$节点可以继续往上走，使得答案增加。$sum[i][j]$是不包含$u$节点权值的，它只保存了$u$往上走所经历的权值和。

每加一个点处理一次，我们就处理一次这个点往上走的最大距离以及所能达到的父节点。询问的就和前面类似了。直接查询$sum[u][j]<X$,满足的话，$u$往上走，往上走的点都是满足权值比当前节点大的。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 4e5 + 10;
const int up = 20;
const ll inf = 1e18;
int  tot,m;
ll last,p,q;
ll w[N], s[N][25];
int fat[N][25];
void add(int p, int q)
{
	w[++tot] = q;
	if (w[tot] <= w[p]){
		fat[tot][0] = p;
	}
	else{
		for (int j = up; j >= 0; j--)
		{
			if (w[fat[p][j]] < w[tot]) p= fat[p][j];
		}
		fat[tot][0] = fat[p][0];
	}
	if (fat[tot][0] == 0){
		s[tot][0] = inf;
	}
	else{
		s[tot][0] = w[fat[tot][0]];
	}
	for (int j = 1; j <= 20; j++)
	{
		fat[tot][j] = fat[fat[tot][j - 1]][j - 1];
		s[tot][j] = fat[tot][j] == 0 ? inf : s[tot][j - 1] + s[fat[tot][j - 1]][j - 1];
	}
}
ll query(int v, ll sum)
{
	ll ans = 0;
	if (sum >= w[v])
	{
		sum -= w[v];
		ans++;
		for (int j = 20; j >= 0; j--)
		{
			if (s[v][j] <= sum){
				ans += (1 << j);
				sum -= s[v][j];
				v = fat[v][j];
			}
		}
	}
	return ans;
}
int main()
{
	w[0] = inf;
	tot = 1;
	scanf("%d", &m);
	memset(s[1], 0x7f, sizeof(s[1]));
	while (m--)
	{
		int op;
		scanf("%d%lld%lld", &op, &p, &q);
		p ^= last,q ^= last;
		if (op==1) add(p, q);
		else printf("%d\n", last = query(p, q));
	}
	return 0;
}