《P10438 [JOISC 2024 Day3] 塔楼》解题报告

· · 题解

一蓑烟雨里 春光不觉老

折扇挑珠帘 依稀闻童谣

东风却远送 小径人寥寥

桃花探杯中 谁家女郎笑

—————⌈岁时记⌋

没人发题解，我来水一发。

首先容易想到对于 D\times A\le B 以及 D\times A>B 的情况分开来讨论。

我们先来考虑 D\times A\le B 的情况，这种情况相对好处理很多。

容易知道，我们的图是若干段不施工的区域合并起来的，我们记 l_i,r_i 分别表示第 i 段不施工的区域。

那么我们现在想尽可能的少用操作 2，考虑记 cnt_i 表示走到第 i 段至少要用多少次 2 操作，不过需要注意，对于第 i 段而言，可能会出现一段前缀是无法到达的，我们记 L_i 表示第 i 段施工的区域可以被到达的最左边的位置。

然后对于询问 x，我们二分出它在哪一段不施工区域中，然后判断一下可达性即可。

这一部分的复杂度是 O(n\log n) 的，也是相对简单的。

接下来考虑 D\times A>B 的情况，这种情况我们需要尽可能多的使用 2 操作。

显然只有在某个 [L_i,r_i] 中的位置才是有用的。

我们考虑动态规划，记 f_i 表示到 i 最多使用多少次操作 2。

考虑一个块中的 f 长什么样。

看上去好像是上面这么一回事，f_{x+D} 直接就是 f_x+1，但是实际上 f_{x+D} 可以直接从 f_{x+D-1} 转移过来，所以还是非常难做。

我们现在卡住了，没有更多很好的想法了，找点性质。

一个段中前 D 个元素，记他为第 y 个，满足 f_{1\sim y}=x,f_{y+1\sim D}=x+1

考虑证明（证明比较感性，不严谨，看看就好了，不看也可以，直接跳了）：

假设 f_y=x,f_{y+1}=x+k(k>1)，考虑本质上为什么 f_y 会比 f_{y+1} 少，因为我们 1 操作走了太多了，也就是 1 操作浪费了太多步数。

我们记 g_y 表示 y 执行 1 的次数，g_{y+1} 为 y+1 执行 y 的次数，那么 f_{y+1}-f_y=k，也就是说 g_{y+1}-g_y\ge D，而倘若浪费的步数比 y+1 的方案多 D，那么实际上我们是可以在中途切换到 y+1 的方案，可以看下面这个图。（因为我们想要观察的是 g_y,g_{y+1} 的相对性，所以我们钦定 g_{y+1}=0。）

我们倒着看，绿色点表示红色要走到这点才能进行二操作，也就是要浪费绿色点和红色点间距离的 1 操作，那么当浪费的操作 \ge D 时，就可以碰到 y+1 路径上的点了，也就说明按 y+1 那样走是可以更新到我们原本 y 路径上的点的，同时还能少浪费 D 次 1 操作。所以是对的。

也就是一个段前 D 个元素中存在一个分界点使其左边的 f 为 x，右边的 f 为 x+1。

而因为值只差 1，所以我们可以直接令 f_{x+D} 从 f_x+1 转移过去，一定不劣。

所以我们现在对于一个段只需要求前 D 个元素即可，所以实际上我们就是要找到那个分界点，因为有单调性，考虑二分。

而对于一个段的前 D 个元素因为我们不知道他的前驱在哪个元素，所以对于 i 而言，要查询 i-D 在哪个段中。

所以实际上实现出来是一个二分套二分的形式，计算是简单的，对于每个段记 pos_i 表示分界点。

然后查询的话我们是可以做到 O(\log n) 单次查询的。

预处理需要 O(n\log^2n) 的复杂度。

所以这种情况的时间复杂度为 O(n\log ^2n)。

总时间复杂度为 O(n\log^2n)。

代码写起来没什么细节。

#include<bits/stdc++.h>
#define Yzl unsigned long long
#define mp make_pair
#define pi pair<LL,LL>
#define fi first
#define se second
#define pb emplace_back
typedef long long LL;

using namespace std;

const Yzl Lty=20120712;

const int MAXN=2e5+10;
const LL inf=1e13;
int n,Q,cnt; 
LL D,A,B;
struct ddl {
    LL l,r;
}a[MAXN],b[MAXN],c[MAXN];
LL f[MAXN];
void sub1() {
    while(Q--) {
        LL x; scanf("%lld",&x);
        LL l=0,r=cnt+1,mid;
        while(l+1<r) { mid=(l+r)/2;
            if(c[mid].r<x) l=mid;
            else r=mid;
        }
        if(c[r].l>x||r==cnt+1) puts("-1");
        else printf("%lld\n",x*A+f[r]*(B-A*D));
    }
}
LL pos[MAXN];
LL erfind(LL x) {
    LL l=0,r=cnt+1,mid;
    while(l+1<r) { mid=(l+r)/2;
        if(c[mid].r<x) l=mid;
        else r=mid;
    }
    if(r==cnt+1||c[r].l>x) x=c[--r].r;
    return f[r]+(x-c[r].l)/D+((x-c[r].l)%D>=pos[r]);
}
void sub2() {
    f[1]=0; pos[1]=D;
    for(int i=2;i<=cnt;++i) {
        LL ls=erfind(c[i].l-D)+1; f[i]=ls;
        LL l=c[i].l,r=min(c[i].r,c[i].l+D-1)+1,mid;
        while(l+1<r) { mid=(l+r)/2;
            if(erfind(mid-D)==ls) r=mid;
            else l=mid;
        } pos[i]=r-c[i].l;
    }
    while(Q--) {
        LL x; scanf("%lld",&x);
        LL l=0,r=cnt+1,mid;
        while(l+1<r) { mid=(l+r)/2;
            if(c[mid].r<x) l=mid;
            else r=mid;
        }
        if(r==cnt+1||c[r].l>x) puts("-1");
        else printf("%lld\n",x*A+(f[r]+(x-c[r].l)/D+((x-c[r].l)%D>=pos[r]))*(B-A*D));
    }
}
int main () {
    scanf("%d%d%lld%lld%lld",&n,&Q,&D,&A,&B);
    for(int i=1;i<=n;++i) {
        scanf("%lld%lld",&a[i].l,&a[i].r);
    } b[++cnt]=(ddl){0,a[1].l-1}; a[n+1].l=inf;
    for(int i=1;i<=n;++i) b[++cnt]=(ddl){a[i].r+1,a[i+1].l-1};
    int CNT=cnt; c[cnt=1]=b[1]; f[1]=0; int pre=0;
    for(int i=1;i<=CNT;++i) {
        while(pre<=cnt&&c[pre].r+D<b[i].l) ++pre;
        if(pre<=cnt&&c[pre].l+D<=b[i].r) {
            c[++cnt]=(ddl){max(b[i].l,c[pre].l+D),b[i].r};
            f[cnt]=f[pre]+1;
        }
    }
    if(D*A<=B) sub1();
    else sub2();
    return 0;
}