题解：P10438 [JOISC 2024] 塔楼 (Day3)

· · 题解

P10438

现有的两篇题解都是两 \log 的，来一个一 \log 的！(其实差不了太多)

情况一

第一个情况是 D\times A\ge B，也就是说要尽可能少跳。

先编一个 O(V) 的 dp。令 dp_i 表示到达 i 最多跳多少次，那么转移就是 dp_i=\min(dp_{i-1},dp_{i-D}+1)，dp_0=0，不能通过的位置 dp_i=\inf。

优化以上 dp。能通过的位置是一段一段的，先猜一下 dp 值长什么样子。

对于每一段，肯定有一段前缀的 dp 值是 \inf。这是显然的。

继续猜，每一段不是 \inf 的都相同，并且每一段都不小于前一段。这个结论仔细想想也是对的。

首先因为 dp_i 对 dp_{i-1} 取了 \min，所以每一段肯定是不升的。递归证明。新加入一段，令这段的左端点为 l，则 dp_l=dp_{l-D}+1，第一个大于 dp_l 的位置为 x，则 dp_x=\min(dp_{x-1},dp_{x-D}+1)=\min(dp_l,dp_{x-D}+1)<dp_l=dp_{l-D}+1，推出 dp_{x-D}<dp_{l-D}，如果 x-D\ge l，那么肯定不成立，否则因为前面的段都满足条件，因此也不成立。

所以 dp 值的连续段有 O(n) 个，从前往后插入，然后找到第一个能转移到新段落的位置（转移的限制是距离限制状物），维护一个指针即可 O(n) 解决。

情况二

第一个情况是 D\times A<B，也就是说要尽可能多跳。

同样的，考虑 dp，令 dp_i 表示到达 i 最多跳多少次，转移是 dp_i=\max(dp_{i-1},dp_{i-D}+1)，dp_0=0，不能到达的地方 dp 值为 -\inf。

同样的，dp 值不为 -\inf 的位置是 O(n) 个段落，并且每一段不降。

显然的，现在每一段不是全相等了，因为可以对 dp_{i-D}+1 取 \max，所以至少每经过 D 个位置，dp 值会 +1。对于长度大于 D 的段落，其形态必定如同将前 D 个拿来一直复制，并且每往后加一段都整体将 dp 值 +1。

考虑这前 D 个，我们猜想其涨幅不会超过 1。考虑如下更强的命题：对于任意 i,j\in[i+1,i+D],dp_i\not=-\inf,dp_j\not=-\inf，那么都有 dp_j\in[dp_i,dp_i+1]。证明可以递归证明，在 [1,j-1] 都满足情况的条件下，如果 dp_j=dp_{j-1}，那么显然满足条件，如果 dp_j=dp_{j-D}+1，那么有 i\in[j-D,j-1] 也就是 i\in[(j-D),(j-D)+D-1]，如果 i=j-D，那么 dp_j=dp_i+1，否则 dp_i\in(dp_{j-D},dp_{j-D}+1)，一样可以证明。

于是 dp 值又被刻画出来了，每一段都是不降的，且段与段之间也是不降的，每一段的 dp 值形态是长为 x\le D 的某个值，然后每 D 格 dp 值 +1。

维护每段端点，开头的值，开头的长度，添加一段的时候通过二分算出开头的长度，复杂度 O(n\log n)。

两部分结合起来算 dp，查询二分到对应的段落查询，复杂度 O(n\log n+q\log n)。

代码： 

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,D,A,B,lft,rgt,mid,flg;
pair<int,int>a[200003];
int k1,k2,k3,k4,k5,k6,k7,k8,k9;
struct Segmt{
    int l;
    int r;
    int stv;
    int stlen;
}P[200003];
int totP;
int getval(int num,int pos){
    if(!flg)return P[num].stv;
    if(P[num].stlen==D)return P[num].stv+((pos-P[num].l)/D);
    return P[num].stv+((pos-P[num].l+D-P[num].stlen)/D);
}
signed main(){
    ios::sync_with_stdio(false);
    cin>>n>>q>>D>>A>>B;
    if(A*D>B)flg=1;
    for(int i=1;i<=n;i++)cin>>a[i].first>>a[i].second;
    P[++totP].l=0;P[totP].r=a[1].first-1;P[totP].stv=0;P[totP].stlen=D;
    a[n+1].first=1000000000001ll;
    a[n+1].second=1000000000001ll+D-1;
    for(int i=1,j=0;i<=n;i++){
        int u=a[i].second+1,v=a[i+1].first-1;
        lft=1;rgt=totP;
        while(lft<rgt){
            mid=((lft+rgt)/2);
            if(P[mid].r+D>=u)rgt=mid;
            else lft=mid+1;
        }
        j=lft;
        if(j>totP)continue;
        if(max(P[j].l+D,u)>min(P[j].r+D,v))continue;
        P[++totP].l=max(P[j].l+D,u);P[totP].r=v;P[totP].stv=getval(j,P[totP].l-D)+1;
        if(!flg){P[totP].stlen=0;continue;}
        k1=P[totP].stv-1;
        lft=j;rgt=totP-1;
        while(lft<rgt){
            mid=((lft+rgt)/2);
            if(getval(mid,P[mid].r)>k1||getval(mid,P[mid].l)>k1)rgt=mid;
            else lft=mid+1;
        }
        if(lft>=totP||lft<j||getval(lft,P[lft].r)==k1){P[totP].stlen=D;continue;}
        int pos=0;
        if(getval(lft,P[lft].l)>k1)pos=P[lft].l;
        else pos=P[lft].l+P[lft].stlen+D*(k1-P[lft].stv);
        pos+=D;
        if(pos>=P[totP].l&&pos<=P[totP].r)P[totP].stlen=pos-P[totP].l;
        else P[totP].stlen=D;
        if(P[totP].stlen==0)P[totP].stlen=D;
    }
    while(q--){
        cin>>k1;
        lft=1;
        rgt=totP;
        while(lft<rgt){
            mid=((lft+rgt)/2)+1;
            if(P[mid].l<=k1)lft=mid;
            else rgt=mid-1;
        }
        if(P[lft].l<=k1&&P[lft].r>=k1)cout<<A*(k1-getval(lft,k1)*D)+B*getval(lft,k1)<<'\n';
        else cout<<-1<<'\n';
    }
    return 0;
}