CF765F Souvenirs

· · 题解

Link

题目大意：

已知一个长度为 n 的序列 a。询问 m 次，每次询问区间 [l,r] 中 |a_i-a_j| 的最小值。不强制在线。

数据范围：1\le n\le10^5,1\le m\le3\times 10^5,0\le a_i\le 10^9。

这道题容易想到莫队套平衡树的 \mathcal{O}(n\sqrt{n}\log n) 的做法。但是过不去。

翻了下题解发现有 \tt bitset 的乱搞做法，居然可以过去。

这里再写一篇分块的解法。

分块，设块长为 \sqrt{n}。

设 pos_i 表示 a_i 所在的块，L_i 和 R_i 分别表示第 i 块的左右端点。

块内升序排序，并且记录下标。时间复杂度 \mathcal{O}(n\log n)。

设 pre_{i,j}(i\le pos_j) 表示从位置 j 到第 i 块的块首的答案，nxt_{i,j}(pos_j\le i) 表示位置 j 到第 i 块的块尾的答案。

以下只说 pre 数组的求法，nxt 数组同理。

容易求出 pre_{i,j}(i=pos_j)。这里暴力就行了，时间复杂度 \mathcal{O}(n\sqrt n)。注意需要将 pre_{i,L_i} 设成极大值，nxt_{i,R_i} 同理。

考虑如何得到 pre_{i,j}(i\neq pos_j)。

用容斥的思想，可以发现 pre_{i,j}=\min(pre_{i,j-1},pre_{i+1,j},cal(i,j))。其中 cal(i,j) 表示第 i 块与 a_j 的答案。

直接求 cal(i,j) 显然不能 \mathcal{O}(1)。但我们一起算出 L_k 到 R_k 是可以做到 \mathcal{O}(\sqrt{n}) 的。具体是通过排序完的数组，扫一遍就好了。

然后用区间动规的思想合并即可。时间复杂度 \mathcal{O}(n\sqrt n)。

查询时，一个散块加一个整块的答案可以直接得知。考虑如何求两个散块的答案。

其实和预处理一样，把排序完的数组扫一遍就好了。时间复杂度 \mathcal{O}(\sqrt n)。

当 pos_l=pos_r 的时候还需要特判一下。但这里直接 \mathcal{O}(n) 暴力也可以过……

单次查询时间复杂度 \mathcal{O}(\sqrt n)。

然后本题就做完了，时间复杂度 \mathcal{O}((n+m)\sqrt{n})，空间复杂度 \mathcal{O}(n\sqrt{n})。

代码如下：

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int s=0;char c=getchar();
    for(;!isdigit(c);c=getchar());
    for(;isdigit(c);c=getchar())
        s=s*10+c-'0';
    return s;
}
int n,m,a[100005];
pair<int,int>b[100005];
int len,block,L[320],R[320],pos[100005];
int pre[320][100005],nxt[320][100005];
int ans[100005];
void get_ans(int p,int q)
{
    int pos=L[p];
    for(int i=L[q];i<=R[q];i++)
    {
        int x=b[i].first;
        while(pos<R[p]&&b[pos+1].first<=x)pos++;
        int y=b[pos].first,z=pos+1>R[p]?y:b[pos+1].first;
        ans[b[i].second]=min(abs(x-y),abs(x-z));
    }
}
void input()
{
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=b[i].first=read(),b[i].second=i;
    len=sqrt(n),block=n/len;
    for(int i=1;i<=block;i++)
        L[i]=R[i-1]+1,R[i]=i*len;
    R[block]=n;
    for(int i=1;i<=block;i++)
    {
        sort(b+L[i],b+R[i]+1);
        for(int j=L[i];j<=R[i];j++)
        {
            pos[j]=i;
            int minn=2e9;
            for(int k=L[i];k<j;k++)
                minn=min(minn,abs(a[j]-a[k]));
            if(j==L[i])pre[i][j]=2e9;
            else pre[i][j]=min(pre[i][j-1],minn);
        }
        for(int j=R[i];j>=L[i];j--)
        {
            int minn=2e9;
            for(int k=R[i];k>j;k--)
                minn=min(minn,abs(a[j]-a[k]));
            if(j==R[i])nxt[i][j]=2e9;
            else nxt[i][j]=min(nxt[i][j+1],minn);
        }
    }
    for(int len=2;len<=block;len++)
    {
        for(int i=1;i+len-1<=block;i++)
        {
            int k=i+len-1;
            get_ans(i,k);
            for(int j=L[k];j<=R[k];j++)
                pre[i][j]=min(pre[i][j-1],min(pre[i+1][j],ans[j]));
        }
        for(int i=block;i-len+1>=1;i--)
        {
            int k=i-len+1;
            get_ans(i,k);
            for(int j=R[k];j>=L[k];j--)
                nxt[i][j]=min(nxt[i][j+1],min(nxt[i-1][j],ans[j]));
        }
    }
}
int temp[320];
inline int query(int l,int r)
{
    int p=pos[l],q=pos[r],res=2e9,pos=1,tot=0;
    if(p==q)
    {
        for(int i=L[p];i<=R[p];i++)
            if(l<=b[i].second&&b[i].second<=r)
                temp[++tot]=b[i].first;
        for(int i=L[p];i<=R[p];i++)
        {
            if(b[i].second<l||r<b[i].second)continue;
            int x=b[i].first;
            while(pos<tot&&temp[pos+1]<=x)pos++;
            int y=pos==1?2e9:temp[pos-1],z=pos+1>tot?y:temp[pos+1];
            res=min(res,min(abs(x-y),abs(x-z)));
        }
        return res;
    }
    for(int i=L[q];i<=R[q];i++)
        if(L[q]<=b[i].second&&b[i].second<=r)
            temp[++tot]=b[i].first;
    for(int i=L[p];i<=R[p];i++)
    {
        if(b[i].second<l||R[p]<b[i].second)continue;
        int x=b[i].first;
        while(pos<tot&&temp[pos+1]<=x)pos++;
        int y=temp[pos],z=pos+1>tot?y:temp[pos+1];
        res=min(res,min(abs(x-y),abs(x-z)));
    }
    return min(res,min(nxt[q-1][l],pre[p+1][r]));
}
void solve()
{
    m=read();
    while(m--)
    {
        int l=read(),r=read();
        printf("%d\n",query(l,r));
    }
}
int main()
{
    input();
    solve();
    return 0;
}