AtCoder Beginner Contest 428 F - Pyramid Alignment 题解

难度：2073

似乎全用线段树+二分写的。不过这种方法确实比较直接。这里提供一种实现也许更加简单的方法，单调栈+二分。

发现实际上我们拥有了 w 数组之后，要掌握所有的区间信息只需要找到一些 拐点。这里 拐点 的意思即对应 1 操作和 2 操作。在平面上两个操作相当于把一段前缀区间分别全部向左和向右靠拢，而靠拢的位置即给出的 v 就是我们要维护的 拐点。

然后我们会发现，维护的拐点若按照区间大小降序排序，有可能会出现“……左，左……”或”……右，右……“的情况，此时只需要保留最大区间所代表拐点即可，其他都可以删去。也就是实际上我们要维护的拐点按照区间大小降序排序必然形如“左，右，左，右……“交替循环下去。那么这个东西+修改可以用一个单调栈维护。每次查询的时候找到包含最小的拐点，然后在拐点二分就好。有一些实现上的细节（如数值处理细节）会在代码中标注。

int n,q,w[N],sta[N],top,pos[N];
bool check(int p,int x){// 判断点 x+0.5 是否在拐点 p 内
    if(p&1)return pos[p]<=x&&x<pos[p]+w[sta[p]];
    return pos[p]-w[sta[p]]<=x&&x<pos[p];
}
int query(int x){// 查询
    int l=1,r=top,res=1;
    while(l<=r){// 二分 1 - 拐点
        int mid=(l+r)/2;
        if(check(mid,x))res=mid,l=mid+1;
        else r=mid-1;
    }
    int p=sta[res];
    if(res&1)x-=pos[res];// 翻转区间
    else x=pos[res]-(x+1);
    l=1,r=p,res=p;
    while(l<=r){// 二分 2 - 拐点内具体编号
        int mid=(l+r)/2;
        if(x<w[mid])res=mid,r=mid-1;
        else l=mid+1;
    }
    return res;
}
int main(){
    n=read();
    REP(i,1,n)w[i]=read();w[n+1]=inf;// 添加 n+1 号点方便处理
    sta[++top]=n+1,pos[top]=0;// 这里 sta 维护拐点区间标号，pos 维护拐点位置
    // 第一个默认左拐点
    q=read();
    REP(i,1,q){
        int type=read(),x=read();
        if(type==1){
            while(x>=sta[top])--top;// 遇到之前较小区间拐点直接删掉，下同
            if(top%2==0)sta[++top]=x,pos[top]=pos[top-1]-w[x];// 注意要保持“左，右，……”的形态
        }else if(type==2){
            while(x>=sta[top])--top;
            if(top%2==1)sta[++top]=x,pos[top]=pos[top-1]+w[x];
        }else if(type==3)write(n+1-query(x)),putchar('\n');// 注意 query 求的是编号，而答案时后缀长度
    }
    return 0;
}