[CF500E]New Year Domino

500E:New Year Domino

题意简述

现在有 n 个多米诺骨牌，从左到右，坐标和高度分别为xi,li，保证 x1<x2<...<xn
一个骨牌能碰倒另一个骨牌当切仅当 xi+li≥xj 。
你可以花费 1 的代价使得某个骨牌长高1高度。
给出 q 个询问，每个询问包含两个数u,v表示向右碰倒 u ，至少需要多少代价才能传递到v
保证 1≤u<v≤n

数据范围

1≤n≤2∗105
1≤q≤2∗105
1≤xi,li≤109

思路

可以发现对于某一个骨牌来说，能碰倒的分到一段，它右边的骨牌被分成了若干段的。
首先利用线段树求出每个点向右碰倒的最远位置rightmax，顺便求出第一个碰不到的骨牌(右边第一段的段首)。
然后利用倍增，求出两个数组。
next[i][j] 表示 i 向右到它第2j段的段的段首的编号。
cost[i][j] 表示 i 到next[i][j]的最少花费。
询问就可以倍增查询了。
总时间复杂度 O((n+q)logn)

UPD:
直接线段树也能做呀= =
离散化之后，每一个骨牌就是一个区间覆盖。
查询的话直接查询两个骨牌之间未被覆盖的个数就行啦。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int in()
{
char ch=getchar();
while (ch<'0'||ch>'9')
ch=getchar();
int ret=0;
while (ch>='0'&&ch<='9')
ret=ret*10+ch-'0',ch=getchar();
return ret;
}
int n,u,v,q,ans,pos,tmp;
int seq[200010],len[200010],rightmax[200010],next[200010][19],cost[200010][19];
namespace Segtree
{
struct Node{
int maxx;
};
Node tree[800010];
void pushup(int node)
{
tree[node].maxx=max(tree[node<<1].maxx,tree[node<<1|1].maxx);
}
void build(int l,int r,int node)
{
if (l==r)
{
tree[node].maxx=rightmax[l];
return;
}
int mid=(l+r)>>1;
build(l,mid,node<<1);
build(mid+1,r,node<<1|1);
pushup(node);
}
void modify(int pos,int l,int r,int node,int val)
{
if (l==r)
{
tree[node].maxx=max(tree[node].maxx,val);
return;
}
int mid=(l+r)>>1;
if (pos<=mid)
modify(pos,l,mid,node<<1,val);
else
modify(pos,mid+1,r,node<<1|1,val);
pushup(node);
}
int getmax(int L,int R,int l,int r,int node)
{
if (L<=l&&r<=R)
return tree[node].maxx;
int mid=(l+r)>>1;
int ret=0;
if (L<=mid)
ret=max(ret,getmax(L,R,l,mid,node<<1));
if (R>mid)
ret=max(ret,getmax(L,R,mid+1,r,node<<1|1));
return ret;
}
}
void init()
{
n=in();
for (int i=1;i<=n;i++)
seq[i]=in(),len[i]=in();
}
void work()
{
for (int i=1;i<=n;i++)
rightmax[i]=seq[i]+len[i];
Segtree::build(1,n,1);
for (int i=n;i>=1;i--)
{
pos=min(n,upper_bound(seq+1,seq+n+1,rightmax[i])-seq-1);
tmp=0;
tmp=Segtree::getmax(i,pos,1,n,1);
rightmax[i]=tmp;
Segtree::modify(i,1,n,1,rightmax[i]);
next[i][0]=min(n,upper_bound(seq+1,seq+n+1,rightmax[i])-seq);
cost[i][0]=max(0,seq[next[i][0]]-rightmax[i]);
}
for (int i=1;i<=18;i++)
for (int j=1;j<=n;j++)
{
next[j][i]=next[next[j][i-1]][i-1];
cost[j][i]=cost[next[j][i-1]][i-1]+cost[j][i-1];
}
q=in();
for (int i=1;i<=q;i++)
{
u=in(),v=in();
ans=0;
for (int j=18;j>=0;j--)
if (next[u][j]<=v)
{
ans+=cost[u][j];
u=next[u][j];
}
printf("%dn",ans);
}
}
int main()
{
init();
work();
return 0;
}

最后

以上就是爱笑棉花糖为你收集整理的[CF500E]New Year Domino的全部内容，希望文章能够帮你解决[CF500E]New Year Domino所遇到的程序开发问题。

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