CF477E 题解

DaiRuiChen007 · 2023-04-24 13:56:52 · 题解

CF477E 题解

题目大意

给定一个 n 行的文档，第 i 行的长度为 a_i，你有一个光标所处位置为 (r,c)，每次可以以如下 6 种方式之一移动：

数据范围：$n,q\le 4\times 10^5$。

思路分析

没有 \mathbf{End} 的情况

先考虑 r_1 和 r_2 的关系，不妨假设 r_1\le r_2，否则可以考虑将 a_1\sim a_n 翻转后再计算，容易证明上述 6 中操作可以在翻转后找到一一对应的操作。因此我们只需要考虑 r_1\le r_2 的情况，下同。

只使用 \mathrm{Down} 和 \mathrm{Left}/\mathrm{Right}

容易发现最优策略一定是先用 \mathrm{Down} 走到第 r_2 行然后再用 \mathrm{Left}/\mathrm{Right} 横向移动，这样可以避免向下过程中的移动损失。

因此此时的答案应该是 r_2-r_1+|\min\{\min[r_1,r_2],c_1\}-c_2|，其中 \min[r_1,r_2] 表示 a_{r_1},a_{r_1+1},\dots a_{r_2} 中的最小值。
使用了 \mathrm{Home}

容易发现多次使用 \mathrm{Home} 只会被抵消，最优解一定是在 r_1 使用 \mathrm{Home}，然后下行到 r_2 然后用 \mathrm{Right} 横向移动。

此时答案为 r_2-r_1+c_2+1。

使用了 \mathbf{End} 的情况

使用了 \mathrm{End}

根据分析，我们知道此时 \mathrm{End} 恰使用一次，且 \mathrm{Home} 不会被使用，原因是 \mathrm{Home} 和 \mathrm{End} 会互相抵消，且这样的抵消是无视剩下 4 种操作的，我们只需要保留最后一个位置即可。

假设我们在第 r_0 行使用 \mathrm{End}，那么最终我们所在的列应该是 \min[r_0,r_2]，答案为 r_2-r_1+|c_2-\min[r_0,r_2]|+1。

由于纵向的移动距离是确定的，因此我们要最小化 c_2-\min[r_0,r_2]。
- c_2\ge \min[r_0,r_2]
  此时我们要找到 \min[r_0,r_2]\le c_2 且 \min[r_0,r_2] 最大的 r_0，容易发现根据 \min[r_0,r_2] 的单调性，我们只需要最小化 r_0 并且保证 \min[r_0,r_2]\le c_2 即可，可以直接二分 r_0 的位置，\min[r_0,r_2] 可以用 ST 表加速 \mathcal O(1) 求出。
- c_2<\min[r_0,r_2]
  此时的 \min[r_0,r_2]>c_2 且 r_0 应该尽可能大，观察容易发现此时的 r_0 应该是 c_2\ge \min[r_0,r_2] 情况中二分出的 r_0 的下一行，即 r_0+1，在二分出上一种情况的 r_0 后顺便计算这种情况即可。

向下绕行的情况

向下绕行，且使用了 \mathrm{End}

同理，\mathrm{End} 只会恰好使用一次，设使用时的所在行为 r_0，显然 r_2\le r_0\le n。

此时的代价为 (r_0-r_1)+(r_0-r_2)+|c_2-\min[r_2,r_0]|+1。
- \min[r_2,r_0]\le c_2
  类似前一种情况，最小化 2r_0-\min[r_2,r_0]，此时 2r_0 和 -\min[r_2,r_0] 都关于 r_0 递增，因此直接最小化 r_0，考虑用情况 3 类似的策略 ST 维护二分判定即可。
- \min[r_2,r_0]>c_2
  此时最小化的式子为 2r_0+\min[r_2,r_0]，并且 r_0<r'_0，r'_0 为上一种情况二分出的最小 r_0。
  
  注意到这个式子两项随着 r_0 增大分别增大和减小，直接用 r'_0-1 肯定不优，考虑一个观察：对于最优解中的 r_0 一定有 \min[r_2,r_0]=a_{r_0} 否则将 a_{r_0} 缩小到 \min[r_2,r_0] 所在行，第一项减小，第二项不变，显然调整后更优。
  
  因此我们只需要维护 [r_2,r'_0) 中最小的 2i+a_i，直接 ST 表维护即可。
向下绕行，且未使用 \mathrm{End}

考虑最终得到的列应该是 \min\{c_0,\min[r_2,r_0]\}，其中 c_0=\min\{c_1,\min[r_1,r_2]\}，表示只用 \mathrm{Down} 操作走到第 r_2 行所在的列标号。
- c_0< c_2
  此时向下绕行只会使 c 单调减小从而使 |c-c_2| 的代价增加，显然这种策略一定不优，因此此时不需要向下绕行。
- c_0\ge c_2
  - c_0<\min[r_2,r_0]
  此时向下绕行操作不会改变 c 的值，并且额外带来纵向移动的代价，此时一定不优。
  
  并且由于对于任意 r_0 均有 \min[r_2,r_0]>c_0\ge c_2，那么说明在向下绕行后使用 \mathrm{End} 得到的列也不会优于直接从 r_1 走到 r_0，因此此时向下绕行的任何决策都是不优的。
  - c_0\ge \min[r_2,r_0]
  此时从 (r_2,c_0) 向下不使用 \mathrm{End} 的效果和使用 \mathrm{End} 完全等效，分类讨论和贡献计算完全相等，只不过节省了一次用 \mathrm{End} 操作的 +1 代价。
综上所述，在实际实现中，我们只需要比较 c_0 和 c_2 的大小判断是否需要执行 \mathrm{End} 操作即可。

向上绕行的情况

同上一种，考虑向上二分 \min[r_0,r_2]\le c_2 的最大行，ST 表维护 a_i-2i 的最值，根据 c_0 与 c_2 的关系判断是否执行 \mathrm{End} 操作。

这种情况不是无意义的，考虑如下数据：

最优答案为 3，操作序列是 \mathrm{Up}\to\mathrm{Down}\to\mathrm{Down}，即向上绕路后使得所在列为 3 从而减少横向移动。

总结

综上所述，我们需要维护三个 ST 表表示 a_i,a_i+2i,a_i-2i 的最值，询问时需要进行二分。

时间复杂度 \mathcal O((n+q)\log n)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=4e5+1;
struct RMQ {
    int f[MAXN][20];
    inline int bit(int x) { return 1<<x; }
    inline void build(int *a,int n) {
        for(int i=1;i<=n;++i) f[i][0]=a[i];
        for(int k=1;k<20;++k) {
            for(int i=1;i+bit(k-1)<=n;++i) {
                f[i][k]=min(f[i][k-1],f[i+bit(k-1)][k-1]);
            }
        }
    }
    inline int query(int l,int r) {
        int k=__lg(r-l+1);
        return min(f[l][k],f[r-bit(k)+1][k]);
    }
}   A,U,D; //a[i], a[i]-2i, a[i]+2i
struct Query {
    int r1,c1,r2,c2,id;
    Query(int _r1=0,int _c1=0,int _r2=0,int _c2=0,int _id=0):
        r1(_r1),c1(_c1),r2(_r2),c2(_c2),id(_id) {}
};
int a[MAXN],u[MAXN],d[MAXN],res[MAXN];
signed main() {
    int n,q;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),u[i]=a[i]-2*i,d[i]=a[i]+2*i;
    scanf("%d",&q);
    vector <Query> P,Q;
    for(int i=1;i<=q;++i) {
        int r1,c1,r2,c2;
        scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
        if(r1<=r2) P.push_back(Query(r1,c1,r2,c2,i));
        else Q.push_back(Query(n-r1+1,c1,n-r2+1,c2,i));
    }
    auto solve=[&](const vector <Query> Q) -> void {
        for(auto q:Q) {
            int r1=q.r1,r2=q.r2,c1=q.c1,c2=q.c2,c0=min(c1,A.query(r1,r2)),mov=(c0>=c2)?0:1;
            int ans=(r2-r1)+c2+1;
            ans=min(ans,(r2-r1)+abs(c2-c0));
            auto Find1=[&](int r1,int r2) -> int {
                int l=r1,r=r2,res=r1-1;
                while(l<=r) {
                    int mid=(l+r)>>1;
                    if(A.query(mid,r2)<=c2) res=mid,l=mid+1;
                    else r=mid-1;
                }
                return res;
            };
            int r0=Find1(r1,r2);
            if(r0>=r1) ans=min(ans,(r2-r1)+(c2-A.query(r0,r2))+1);
            if(r0<r2) ans=min(ans,(r2-r1)+(A.query(r0+1,r2)-c2)+1);
            auto Find2=[&](int r1,int r2) -> int {
                int l=r2,r=n,res=n+1;
                while(l<=r) {
                    int mid=(l+r)>>1;
                    if(A.query(r2,mid)<=c2) res=mid,r=mid-1;
                    else l=mid+1;
                }
                return res;
            };
            r0=Find2(r1,r2);
            if(r0<=n) ans=min(ans,(r0-r1)+(r0-r2)+(c2-A.query(r2,r0))+mov);
            if(r0>r2) ans=min(ans,D.query(r2,r0-1)-r1-r2-c2+mov);
            auto Find3=[&](int r1,int r2) -> int {
                int l=1,r=r1,res=0;
                while(l<=r) {
                    int mid=(l+r)>>1;
                    if(A.query(mid,r2)<=c2) res=mid,l=mid+1;
                    else r=mid-1;
                }
                return res;
            };
            r0=Find3(r1,r2);
            if(r0>=1) ans=min(ans,(r1-r0)+(r2-r0)+(c2-A.query(r0,r2))+mov);
            if(r0<r1) ans=min(ans,U.query(r0+1,r1)+r1+r2-c2+mov);
            res[q.id]=ans;
        }
    };
    A.build(a,n),U.build(u,n),D.build(d,n);
    solve(P);
    reverse(a+1,a+n+1);
    for(int i=1;i<=n;++i) u[i]=a[i]-2*i,d[i]=a[i]+2*i;
    A.build(a,n),U.build(u,n),D.build(d,n);
    solve(Q);
    for(int i=1;i<=q;++i) printf("%d\n",res[i]);
    return 0;
}