欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Educational Codeforces Round 66 (Rated for Div. 2)-E. Minimal Segment Cover

程序员文章站 2023-12-25 18:30:57
...

Educational Codeforces Round 66 (Rated for Div. 2)-E. Minimal Segment Cover

地址:https://codeforces.com/contest/1175/problem/E

思路:倍增DP

dp[i][j]表示以i为起点走 2^j 条线段能够到达的最远位置,那么

dp[i][j]=dp[dp[i][j-1]][j-1]

对于每次询问,j由大到小判断即可

Code:

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int MAX_S=5e5+5;
int n,m,lm;
int dp[MAX_S][20];

int Query(int l,int r);
int main()
{
	scanf("%d%d",&n,&m);
	int l,r,mr=0;
	for(int i=0;i<n;++i)
	{
		scanf("%d%d",&l,&r);
		dp[l][0]=max(dp[l][0],r);
		mr=max(mr,r);
	}
	lm=log2(mr);
	for(int i=1;i<=mr;++i)
		dp[i][0]=max(dp[i][0],max(i,dp[i-1][0]));
	for(int j=1;(1<<j)<=mr;++j)
		for(int i=0;i<=mr;++i)
			dp[i][j]=dp[dp[i][j-1]][j-1];
	for(int i=0;i<m;++i)
	{
		scanf("%d%d",&l,&r);
		printf("%d\n",Query(l,r));
	}
	
	return 0;
}

int Query(int l,int r)
{
	int res=0;
	for(int j=lm;j>=0;--j)
		if(dp[l][j]!=l&&dp[l][j]<r){
			l=dp[l][j];	res+=(1<<j);
		}
	l=dp[l][0];	++res;
	if(l<r)	res=-1;
	return res;
}

 

上一篇:

下一篇: