题解：CF515E Drazil and Park

ny_Dacong · 2025-07-27 17:24:57 · 题解

思路

首先看到环，考虑断环成链。这样可以方便使用一些处理序列问题的手段。

接着看我们要求的式子：

距离可以试着用前缀和优化。设前缀和数组 s，s_i 表示第 i 棵树与第一棵树的距离。式子可以化为：

考虑将这个式子最大化。即 (s_y + 2h_y) 最大，(s_x - 2h_x) 最小。因此维护这两个值，套用 RMQ 的模板即可。

:::warning[注意：不能选同一棵树] 中文翻译得比较随意，没有提出这一点，但英文题面明确说是“Drazil chooses two different trees”。

所以建议做 CF 的题的时候还是看一看英文题面，不要过度依赖翻译。 :::

因此如果最后选的是同一棵树 p，则还要在 [l \sim p-1] 中再查询一遍最小值 p_1，在 [p+1 \sim r] 中再查询一遍最大值 p_2。

不过最终答案并非就是 [p_1 \sim p_2]，还有可能是 [p_1 \sim p] 或 [p \sim p_2]。取最大即可。

实现

本题时限 2s，空限 512MB。时间较为宽松但空间对于 ST 表来说并不算大。再考虑到 ST 表边界问题处理起来比较麻烦，所以我们使用线段树维护。

还有一个注意点，我们分析时 s_i 表示第 i 棵树与第一棵树的距离，但是题目给的是第 i 棵树与它后面那棵树的距离，所以读入时 i 要加一。

AC 代码

:::success[AC 代码（线段树）]

#include<bits/stdc++.h>
using namespace std;
long long n,m;
long long num[200050],sum[200050][2];
long long tree[200050<<2][2];
long long ls(long long x){
    return x<<1;
}
long long rs(long long x){
    return x<<1|1;
}
void push_up(long long p){
    tree[p][0] = sum[tree[ls(p)][0]][0] <= sum[tree[rs(p)][0]][0] ? tree[ls(p)][0] : tree[rs(p)][0];
    tree[p][1] = sum[tree[ls(p)][1]][1] > sum[tree[rs(p)][1]][1] ? tree[ls(p)][1] : tree[rs(p)][1];
    return;
}
void build(long long p,long long pl,long long pr){
    if(pl == pr){
        tree[p][0] = tree[p][1] = pl;
        return;
    }
    long long mid = pl+((pr-pl)>>1);
    build(ls(p),pl,mid);
    build(rs(p),mid+1,pr);
    push_up(p);
    return;
}
long long query(long long p,long long pl,long long pr,long long l,long long r,long long opt){
    if(l <= pl && pr <= r){
        return tree[p][opt];
    }
    long long mid = pl+((pr-pl)>>1);
    long long res1 = -1,res2 = -1;
    if(l <= mid){
        res1 = query(ls(p),pl,mid,l,r,opt);
    }
    if(mid < r){
        res2 = query(rs(p),mid+1,pr,l,r,opt);
    }
    if((~res1) && (~res2)){
        if(opt == 0){
            return sum[res1][0] <= sum[res2][0] ? res1 : res2;
        }else{
            return sum[res1][1] > sum[res2][1] ? res1 : res2;
        }
    }
    if(~res1){
        return res1;
    }
    return res2;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(long long i = 1; i <= n; i++){
        scanf("%lld",&num[i+1]);
        num[i+n+1] = num[i+1];
    }
    num[1] = num[(n<<1)+1];
    num[(n<<1)+1] = 0;
    for(long long i = 1; i <= (n<<1); i++){
        sum[i][0] = sum[i][1] = sum[i-1][0]+num[i];
    }
    for(long long i = 1; i <= n; i++){
        static long long tp;
        scanf("%lld",&tp);
        tp <<= 1;
        sum[i][1] += tp;
        sum[i][0] -= tp;
        sum[i+n][1] += tp;
        sum[i+n][0] -= tp;
    }
    n <<= 1;
//  for(long long i = 1; i <= n; i++){
//      printf("%4d %4d\n",sum[i][0],sum[i][1]);
//  }
//  puts("------");
    build(1,1,n);
    while(m--){
        static long long tpa,tpb,tpc,tpd,tpe;
        scanf("%lld%lld",&tpa,&tpb);
        tpc = tpd = 0;
        if(tpa <= tpb){
            tpa += (n>>1);
        }
        tpc = query(1,1,n,tpb+1,tpa-1,0);
        tpd = query(1,1,n,tpb+1,tpa-1,1);
        if(tpc == tpd){
            tpe = tpc;
            if(tpe != tpb+1){
                tpc = query(1,1,n,tpb+1,tpe-1,0);
            }
            if(tpe != tpa-1){
                tpd = query(1,1,n,tpe+1,tpa-1,1);
            }
            printf("%lld\n",max({(tpd != tpc ? sum[tpd][1]-sum[tpc][0] : -1),(tpd != tpe ? sum[tpd][1]-sum[tpe][0] : -1),(tpe != tpc ? sum[tpe][1]-sum[tpc][0] : -1)}));
        }else{
            printf("%lld\n",sum[tpd][1]-sum[tpc][0]);
        }
    }
    return 0;
}

:::

AC 记录

没想到我之前做过一遍这道题（不过全忘干净了）。当时用的 ST 表，这里一并贴上来。

:::success[AC 代码（ST 表）]

#include<bits/stdc++.h>
using namespace std;
long long n,m,logmax;
long long d[200050],num[200050],a[200050],b[200050];
long long Max[200050][20],Min[200050][20];
long long getans(long long l,long long r){
    long long len = log2(r-l+1);
    long long x,y,p,q;
    x = a[Min[l][len]] < a[Min[r-(1<<len)+1][len]] ? Min[l][len] : Min[r-(1<<len)+1][len];
    y = b[Max[l][len]] > b[Max[r-(1<<len)+1][len]] ? Max[l][len] : Max[r-(1<<len)+1][len];
    if(x != y){
        return b[y]-a[x];
    }
    x--;
    if(x-l+1 > 0){
        len = log2(x-l+1);
        p = a[Min[l][len]] < a[Min[x-(1<<len)+1][len]] ? Min[l][len] : Min[x-(1<<len)+1][len];
    }else{
        y++;
        len = log2(r-y+1);
        q = b[Max[y][len]] > b[Max[r-(1<<len)+1][len]] ? Max[y][len] : Max[r-(1<<len)+1][len];
        return b[q]-a[y-1];
    }
    y++;
    if(r-y+1 > 0){
        len = log2(r-y+1);
        q = b[Max[y][len]] > b[Max[r-(1<<len)+1][len]] ? Max[y][len] : Max[r-(1<<len)+1][len];
    }else{
        return b[x+1]-a[p];
    }
    return max(b[x+1]-a[p],b[q]-a[y-1]);
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(long long i = 1; i <= n; i++){
        if(i == n){
            scanf("%lld",&d[1]);
        }else{
            scanf("%lld",&d[i+1]);
        }
    }
    for(long long i = 1; i <= n; i++){
        d[i+n] = d[i];
    }
    d[1] = 0;
    for(long long i = 1; i <= n+n; i++){
        d[i] += d[i-1];
    }
    for(long long i = 1; i <= n; i++){
        scanf("%lld",&num[i]);
        num[i+n] = num[i];
    }
    n <<= 1;
    for(long long i = 1; i <= n; i++){
        a[i] = -((num[i]<<1)-d[i]);
        b[i] = (num[i]<<1)+d[i];
        Min[i][0] = Max[i][0] = i;
    }
    logmax = log2(n);
    for(long long j = 1; j <= logmax; j++){
        for(long long i = 1; i <= n-(1<<j)+1; i++){
            Max[i][j] = b[Max[i][j-1]] > b[Max[i+(1<<(j-1))][j-1]] ? Max[i][j-1] : Max[i+(1<<(j-1))][j-1];
            Min[i][j] = a[Min[i][j-1]] < a[Min[i+(1<<(j-1))][j-1]] ? Min[i][j-1] : Min[i+(1<<(j-1))][j-1];
        }
    }
    while(m--){
        static long long tpa,tpb;
        scanf("%lld%lld",&tpa,&tpb);
        if(tpa <= tpb){
            printf("%lld\n",getans(tpb+1,tpa+n/2-1));
        }else{
            swap(tpa,tpb);
            printf("%lld\n",getans(tpa+1,tpb-1));
        }
    }
    return 0;
}

:::

AC 记录

:::info[后记] 作者写完本文时已经退役快五个月了。暑假闲来没事上洛谷，发现这道题还在我的补题列表上。为了追忆以前的时光，涨涨咕值，顺手试一试洛谷新的 MD，花了一个下午完成了本题。还好，手没生，也算是一点安慰吧。 :::

:::epigraph[——ny_Dacong] Written on July 27th,2025. :::