【CodeForces 500E】New Year Domino / 题解

【CodeForces 500E】New Year Domino / 题解

原题地址

题目描述

给定一列多米诺骨牌的高度和底端横坐标,求若要让推动第x块至少使第y块倒下,需要加长区间内的多米诺骨牌的总长度。

样例

输入
6
1 5
3 3
4 4
9 2
10 1
12 1
4
1 2
2 4
2 5
2 6
输出
0
1
1
2
样例解释

(样例的第四个询问)

思路

倍增。

维护一块骨牌右边最近的碰不到的骨牌编号和距离。

询问直接log累加就行了。。。

代码

#include 
#define maxn 200010
using namespace std;
long long p[maxn][30],d[maxn][30],q[maxn];
long long n,a[maxn],b[maxn],fr;
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i]>>b[i];
    q[++fr]=n+1;a[n+1]=0x777777777777777,b[n+1]=0;
    p[n+1][0]=n+1,d[n+1][0]=0;
    for (int i=n;i>=1;i--){
        while(a[q[fr]]+b[q[fr]]<=a[i]+b[i]) fr--;
        p[i][0]=q[fr];
        d[i][0]=max((long long)0,a[q[fr]]-a[i]-b[i]);q[++fr]=i;
    }
    for (int i=1;i<30;i++)
        for (int x=n+1;x>0;x--){
            p[x][i]=p[p[x][i-1]][i-1];
            d[x][i]=d[x][i-1]+d[p[x][i-1]][i-1];    
        }
    int TAT;cin>>TAT;while(TAT--){
        int l,r,ans=0;cin>>l>>r;
        for (int i=29;i>=0;i--)
            if (p[l][i]<=r) ans+=d[l][i],l=p[l][i];
        cout<
Show Comments