CF765F Souvenirs题解

Iceturky · 2025-01-03 07:59:31 · 题解

询问区间最小差。

离线处理。只考虑 i<j,a_i\leq a_j 的情况

考虑对于 i ，有哪些 j 能造成贡献。

注意到这些 j 是在只保留大于等于 a_i 值后的单调队列样式的单调上升序列。

即为 i 左侧第一个大于等于 a_i 的 a_{j_1} ，a_{j_1} 左侧第一个小于 a_{j_1} 但大于等于 a_i 的 a_{j_2} 等等。

容易发现如果 a_{j_x} 跟 a_{j_y} (j_y<j_x) 间距离小于等于 a_{j_y} 与 a_i 的距离时，i 是不会对 j_y 产生贡献的。因为 [j_y,j_x] 是更优且被严格包含的区间。

可以产生贡献的 a_{j_y} 满足的式子是 a_{j_x}-a_{j_y}> a_{j_y}-a_i 。移项后得 a_{j_y} <\frac{a_{j_x}+a_i}{2} 。

且其一定满足 a_{j_y}\geq a_i 。

用扫描线找一下值域范围内 i 左边最靠右的下标即可。

考虑 a_j-a_i 是每次至少缩小一半的，所以最多有 \mathrm{O(\log{V})} 个位置能贡献到 i 。

前面扫描线有一个 \mathrm{O(\log{n})} ，所以总复杂度就是 \mathrm{O(n\log{n}\log{V}+q\log{n})} 。

code

//省略了两棵线段树。T是单点赋值区间min，T2是单点赋值区间max。

struct Que{
    int l,r,id;
    bool operator<(Que ano)const{
        return r<ano.r;
    }
}Q[N];

int X[N],len;

int a[N];

int ans[N];

void calc(int n,int m){
    T.build(1,1,n);T2.build(1,1,len);T2.n=len;
    for(int i=1,j=1;i<=n;i++){
        int limit=inf;
        while(1){
            int tmp=upper_bound(X+1,X+1+len,limit)-X-1;
            if(X[tmp]<a[i])
                break;
            int nw=T2.query(a[i],tmp);
            if(nw<=0)
                break;
            T.update(nw,X[a[nw]]-X[a[i]]);
            limit=(X[a[nw]]+X[a[i]]+1)/2-1;
        }
        T2.update(a[i],i);
        while(j<=m&&Q[j].r==i){
            ans[Q[j].id]=min(ans[Q[j].id],T.query(Q[j].l,i));
            j++;
        }
        //cout<<i<<endl;
        //for(int k=1;k<=i;k++)
        //  print(T.query(k,k)),pc(' ');pc('\n');
    }//cout<<endl;
}

signed main(){
    int n=read();T.n=n;
    for(int i=1;i<=n;i++)
        X[i]=a[i]=read();
    sort(X+1,X+1+n);len=unique(X+1,X+1+n)-X-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(X+1,X+1+len,a[i])-X;
    int m=read();
    for(int i=1;i<=m;i++){
        int l=read(),r=read();
        Q[i]={l,r,i};
    }
    sort(Q+1,Q+1+m);
    a[0]=-1;
    memset(ans,0x3f,sizeof(ans));
    calc(n,m);
    reverse(a+1,a+1+n);
    for(int i=1;i<=m;i++){
        int l=Q[i].l,r=Q[i].r;
        Q[i].l=n-r+1,Q[i].r=n-l+1;
    }
    sort(Q+1,Q+1+m);
    calc(n,m);
    for(int i=1;i<=m;i++)
        print(ans[i]),pc('\n');
    return 0;
}