倍增+DP

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

Codeforce 1175 EMinimal Segment Cover

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

#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是不包含在我们一步所能到达的区间内的,即我们一步只能得到区间[dp[i][0],r)\left [ dp[i][0],r \right ) . 这个r代表下一步的起点,仔细想想很巧妙。

注意dp[n+1][i](i[1,n])dp[n+1][i](i \in [1 ,n])要设为n+1n+1.因为处理dp[i][0]dp[i][0]的时候可能返回n+1n+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]fat[i][j] 表示ii节点往上走的第2j2^j个父亲,注意这里的父节点不是普通的父节点,而是满足条件的父节,即父节点的权值比子节点大,如果没有点权值比当前节点大,那父节点就是0. sum[i][j]sum[i][j]表示i往上走2j2^j个节点得到的权值和,sum[1][i](i[1,n])sum[1][i](i \in [1 ,n]) 要设为infinf,因为11节点就不能往上走了,设为00的话11节点可以继续往上走,使得答案增加。sum[i][j]sum[i][j]是不包含uu节点权值的,它只保存了uu往上走所经历的权值和。

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

#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;
}