codeforces 500E New Year Domino(线段树预处理+倍增）

【题目链接】

解题思路

先用线段树预处理能达到的最远长度，就是从后往前，对每个点，二分找到它能到的最远的木棒，找到这其中的最远距离，更新。
对每一个点，向推倒它之后第一个不能被波及到的木棒连一条边，记录一个花费。
用dp[i][j]表示第i个点走过2的j次方条边后到达的点，同时记录花费。

 dp[i][j]=dp[dp[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]+cost[dp[i][j-1]][j-1];

之后倍增，j从最大开始（比如这个题我设了个29），只有当dp[i][j]<终点时才跳（因为在dp[i][j]前的都是一定要被跳的），跳完以后特判试是刚好到不了终点还有跳一条边还是已经到了。

AC代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=2e5+7;
int n;
struct node
{
int x,h;
}a[maxn];
bool cmp(node a,node b)
{
if(a.x!=b.x) return a.x<b.x;
else a.h<b.h;
}
int loc[maxn],b[maxn];
int tree[maxn<<2];
int cnt;///建新树前置0
void build(int i,int ll,int rr)
{
if(ll==rr)
{
tree[i]=b[++cnt];
}
else
{
int mid=(ll+rr)/2;
build(i*2,ll,mid);
build(i*2+1,mid+1,rr);
tree[i]=max(tree[i*2],tree[i*2+1]);
}
}
void update(int i,int x,int v,int ll,int rr)
{
if(ll==rr)
{
tree[i]=v;
return;
}
int mid=(ll+rr)/2;
if(x<=mid)
{
update(i*2,x,v,ll,mid);
}
else
{
update(i*2+1,x,v,mid+1,rr);
}
tree[i]=max(tree[i*2],tree[i*2+1]);
}
int quest(int i,int l,int r,int ll,int rr)
{
//printf("%d (%d,%d) (%d,%d)n",i,l,r,ll,rr);
if(ll==l&&rr==r) return tree[i];
int
mid=(ll+rr)/2;
if(r<=mid)
{
return quest(i*2,l,r,ll,mid);
}
else if(l>mid)
{
return quest(i*2+1,l,r,mid+1,rr);
}
else
{
return max(quest(i*2,l,mid,ll,mid),quest(i*2+1,mid+1,r,mid+1,rr));
}
}
int dp[maxn][30],cost[maxn][30];
int main()
{
int i,j,k,x,y,l,r,len,q,ans;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a[i].x,&a[i].h);
}
sort(a+1,a+1+n,cmp);
for(i=1;i<=n;i++)
{
b[i]=a[i].x+a[i].h;
loc[i]=a[i].x;
}
cnt=0;
build(1,1,n);
for(i=n;i>0;i--)
{
b[i]=quest(1,i,upper_bound(loc+i,loc+1+n,b[i])-1-loc,1,n);
update(1,i,b[i],1,n);
}
for(i=1;i<=n;i++)
{
y=upper_bound(loc+i,loc+1+n,b[i])-loc;
if(y>n)
{
y=n;
len=0;
}
else len=a[y].x-b[i];
dp[i][0]=y;
cost[i][0]=len;
}
for(j=1;j<30;j++)
{
for(i=1;i<=n;i++)
{
dp[i][j]=dp[dp[i][j-1]][j-1];
cost[i][j]=cost[i][j-1]+cost[dp[i][j-1]][j-1];
}
}
//
for(i=1;i<=n;i++)
//
{
//
for(j=0;j<30;j++)
//
{
//
printf("dp[%d][%d]=%d cost[%d][%d]=%dn",i,j,dp[i][j],i,j,cost[i][j]);
//
}
//
}
scanf("%d",&q);
while(q--)
{
ans=0;
scanf("%d%d",&l,&r);
i=l;
for(j=29;j>=0;j--)
{
if(dp[i][j]<r)
{
//printf("cost[%d][%d]=%dn",i,j,cost[i][j]);
ans+=cost[i][j];
i=dp[i][j];
}
}
if(dp[i][0]<=r) ans+=cost[i][0];
printf("%dn",ans);
}
return 0;
}

最后

以上就是悦耳纸鹤为你收集整理的codeforces 500E New Year Domino(线段树预处理+倍增）codeforces 500E New Year Domino(线段树预处理+倍增）的全部内容，希望文章能够帮你解决codeforces 500E New Year Domino(线段树预处理+倍增）codeforces 500E New Year Domino(线段树预处理+倍增）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。