题解 CF477E 【Dreamoon and Notepad】

xtx1092515503 · 2020-12-02 18:07:15 · 题解

大毒瘤数据结构题。好不容易自己A掉就来发篇题解。

首先，因为 r_1 和 r_2 的大小关系不确定，故我们可以对于 r_1>r_2 的询问，将 r 变成 n-r+1 并翻转整个序列，将其变成 r_1\leq r_2 的情形。所以我们下面默认 r_1\leq r_2。

然后我们下面考虑画出图来：

假设我们有一个光标，它想从 1 走到 8，应该怎样走呢？

我们发现，无论怎样乱跑，从 1 到 8 的七次向右走（实际上应该是 down 操作，但是因为我把图竖过来了所以就是向右走）总是免不了的。与此同时，向上向下走，我们会发现无论在哪里走都是没有区别的（当然，并非这样——你有可能在某个位置向上向下走了很多，但是往右又走了一些就被一个顶给撞下去了，也就是说提前的上下移动有可能是无用功——所以我们不如直接统一在 r_2 处上下移动）。

那么，上下左右的事情我们都分析过了（不，实际上左右还有其它的可能，但是我们待会再说），就只剩 HOME 和 END 操作了。因为我们把图竖过来了，所以下文统一把 HOME 称作下跳，END 称作上跳。

我们发现，下跳操作，无论在任何位置实行也都是一样的，所以我们也可以统一在 r_2 处处理。就只剩上跳操作了。

我们再回到上图。明显，只有在某些位置的上跳是有意义的——例如，在 4 处的上跳，会马上再被 5 撞下去；而只有 5,7,8 处的上跳，是不会被撞下去的。观察发现，有效的位置可以直接使用单调栈维护。

因为无论在哪个位置上跳需要的操作都是 1 次，所以我们肯定选择在离 c_2 最近的那个位置处上跳。于是我们可以在单调栈中二分，找到离 c_2 最近的两个位置（一个比 c_2 大，一个比 c_2 小），判断哪个位置更优即可。

则我们现在可能使用的策略共可以归纳如下：

在未到终点之前，只执行向右操作。到了终点之后，通过上下操作移到终点。

此部分可以通过二分在单调栈中求出 r_1 在单调栈里的下一个位置（也就是从 r_1 到 r_2 的路径中，其会被撞得最低的一次），然后与 c_1 取 \min 找到到达终点时它的高度，然后上下移动即可。

在未到终点之前，只执行向右操作。到了终点之后，下跳一次，然后上下移动。
在未到终点之前，执行向右操作，并在单调栈上某个位置上跳一次；到终点之后，上下移动。

如上所述，可以通过二分找到最优的上跳点。

到这里似乎没有什么更好的策略了。于是我们兴冲冲把代码写出来，然后一下过了第一组样例，再测第二组，出锅了。我们可以看一下第二组样例：

可以发现，第二组样例的思想，是利用左右移动和上跳来代替上下移动。再回到我们上面那幅图，假如我们想从 2 走到 4 的中部，可能向右走到 5 再走回来反而会更优。

观察发现，这样向左向右移动所走到的位置，必定还是单调栈上的位置。

先考虑从终点出发向右走的情形。我们考虑从 (r_2,fin)，其中 fin 是从 r_1 走到 r_2 的终点，走到其右方的某个位置，设成 R，然后再上跳到位置 C 的距离，发现是

2(R-r_2)+|fin-C|+[fin<C]

其中，前两项是简单的距离；后一项是表示如果需要时，还需要上跳一下。

对于绝对值，我们的套路是把它拆开，然后就可以把它分成两半，一半只与 (r_2,fin) 有关，一半只与 (R,C) 有关。然后使用数据结构维护 (R,C) 即可。这里因为觉得离散化什么的比较麻烦，我就直接上平衡树维护了。

再考虑从起点出发向左走的情形。这里也会发现与前面类似，就不再赘述了——详情可以见代码。

则时间复杂度 O(n\log n)。常数极大，但可以通过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define y1 _19260817
#define y2 _17680321
int n,m,a[400100],stk[400100],res[400100],tp;
struct Query{
    int x1,x2,y1,y2,id;
    Query(int i){scanf("%d%d%d%d",&x1,&y1,&x2,&y2),id=i;}
    friend bool operator <(const Query &x,const Query &y){return x.x2<y.x2;}
};
#define lson t[x].ch[0]
#define rson t[x].ch[1]
int cnt,rt;
struct Treap{
    int ch[2],sz,val,pos,mnp,mnm,rd;
}t[400100];
void pushup(int x){
    t[x].mnp=t[x].val-2*t[x].pos;
    t[x].mnm=-t[x].val-2*t[x].pos;
    t[x].sz=1;
    if(lson)t[x].mnp=min(t[x].mnp,t[lson].mnp),t[x].mnm=min(t[x].mnm,t[lson].mnm),t[x].sz+=t[lson].sz;
    if(rson)t[x].mnp=min(t[x].mnp,t[rson].mnp),t[x].mnm=min(t[x].mnm,t[rson].mnm),t[x].sz+=t[rson].sz;
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(t[x].rd>t[y].rd){t[x].ch[1]=merge(t[x].ch[1],y),pushup(x);return x;}
    else{t[y].ch[0]=merge(x,t[y].ch[0]),pushup(y);return y;}
}
void splitbypos(int x,int k,int &u,int &v){//u:<k.
    if(!x){u=v=0;return;}
    if(t[x].pos<k)u=x,splitbypos(rson,k,rson,v);
    else v=x,splitbypos(lson,k,u,lson);
    pushup(x);
}
void splitbyval(int x,int k,int &u,int &v){//u:<k.
    if(!x){u=v=0;return;}
    if(t[x].val<k)u=x,splitbyval(rson,k,rson,v);
    else v=x,splitbyval(lson,k,u,lson);
    pushup(x);
}
void splitbysize(int x,int k,int &u,int &v){
    if(!x){u=v=0;return;}
    if(t[lson].sz>=k)v=x,splitbysize(lson,k,u,lson);
    else u=x,splitbysize(rson,k-t[lson].sz-1,rson,v);
    pushup(x);
}
int newnode(int x){
    int u=++cnt;
    t[u].ch[0]=t[u].ch[1]=0;
    t[u].pos=x,t[u].val=a[x];
    t[u].rd=rand()*rand();
    pushup(u);
    return u;
}
void Insert(int x){
    int a,b;
    splitbypos(rt,x,a,b);
    rt=merge(merge(a,newnode(x)),b);
}
void Delete(int x){
    int a,b,c;
    splitbypos(rt,x,a,b);
    splitbysize(b,1,b,c);
    rt=merge(a,c);
}
int Ask(int bef,int x,int now){
    int a,b,c,e,f;
    splitbysize(rt,bef-1,b,c);
    splitbyval(b,x,a,b);
    int ret=0x3f3f3f3f;
    splitbyval(a,now+1,e,f);
    ret=min(ret,min(t[e].mnm+x,t[f].mnm+x+1));
    a=merge(e,f);

    splitbyval(b,now+1,e,f);
    ret=min(ret,min(t[e].mnp-x,t[f].mnp-x+1));
    b=merge(e,f);

    rt=merge(merge(a,b),c);
    return ret;
}
void Iterate(int x){
    if(!x)return;
    Iterate(lson);
    printf("[%d:%d]",x,a[x]);
    Iterate(rson);
}
void func(vector<Query>&v){
    sort(v.begin(),v.end());
    tp=0;
    cnt=rt=0;
    for(int i=0,j=1;i<v.size();i++){
//      printf("[%d,%d]\n",v[i].x1,v[i].x2);
        while(j<=v[i].x2){
            while(tp&&a[stk[tp]]>a[j])Delete(stk[tp--]);
            Insert(stk[++tp]=j++);
        }
//      for(int k=1;k<=tp;k++)printf("%d ",stk[k]);puts("");
//      for(int k=1;k<=tp;k++)printf("%d ",a[stk[k]]);puts("");
        int tmp=lower_bound(stk+1,stk+tp+1,v[i].x1)-stk;
        int fin=min(v[i].y1,a[stk[tmp]]);
//      printf("%d,%d\n",tmp,fin);
        res[v[i].id]=min(res[v[i].id],abs(v[i].x1-v[i].x2)+abs(fin-v[i].y2));//do not press anything special

        res[v[i].id]=min(res[v[i].id],abs(v[i].x1-v[i].x2)+v[i].y2+1);//press a HOME somewhere.

        a[n+1]=v[i].y2;
        int pmt=lower_bound(stk+tmp,stk+tp+1,n+1,[](int u,int v){return a[u]<a[v];})-stk;
        res[v[i].id]=min(res[v[i].id],abs(v[i].x1-v[i].x2)+abs(a[stk[pmt]]-v[i].y2)+1);//press an END somewhere in [x1,y1]
        if(pmt>tmp)res[v[i].id]=min(res[v[i].id],abs(v[i].x1-v[i].x2)+abs(a[stk[pmt-1]]-v[i].y2)+1);

        res[v[i].id]=min(res[v[i].id],v[i].x2+v[i].x1+Ask(tmp,v[i].y2,v[i].y1));//move to somewhere in [1,x1), and press an END if need.

        v[i].y1=fin;//stock fin for later use.
    }
    tp=0;
    cnt=rt=0;
    reverse(v.begin(),v.end());
    for(int i=0;i<v.size();i++)v[i].x1=n-v[i].x1+1,v[i].x2=n-v[i].x2+1;
    reverse(a+1,a+n+1);
    for(int i=0,j=1;i<v.size();i++){
        while(j<=v[i].x2){
            while(tp&&a[stk[tp]]>a[j])Delete(stk[tp--]);
            Insert(stk[++tp]=j++);
        }
//      Iterate(rt);puts("");
//      printf("%d %d\n",v[i].y2,v[i].y1);
        res[v[i].id]=min(res[v[i].id],abs(v[i].x1-v[i].x2)+2*v[i].x2+Ask(tp+1,v[i].y2,v[i].y1));//move to somewhere in (x2,n], press an END if need.
    }
    reverse(a+1,a+n+1);
}
vector<Query>v1,v2;
int main(){
    scanf("%d",&n),memset(res,0x3f,sizeof(res)),t[0].mnm=t[0].mnp=0x3f3f3f3f;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        Query q(i);
        if(q.x1<=q.x2)v1.push_back(q);
        else q.x1=n-q.x1+1,q.x2=n-q.x2+1,v2.push_back(q);
    }
    func(v1);
    reverse(a+1,a+n+1);
    func(v2);
    for(int i=1;i<=m;i++)printf("%d\n",res[i]);
    return 0;
}
/*
13
245468 180916 290696 340113 166951 259500 135270 32481 211977 128410 185376 380953 27639
1
1 244718 8 27128
*/