CF765F Souvenirs

(Updated: )
oi

Description

题目链接：CF765F

给定一个长度为 $n$ 的序列 $a_i$，有 $m$ 个询问，每次询问给定 $l,r$，求对于 $i,j\in[l,r]$，且满足 $i\not = j$，$a_i - a_j$ 的最小值。

$1\leq n\leq 10^5,1\leq m\leq 3\times 10^5,0\leq a_i\leq 10^9$。

Solution

分块（感觉 mrsrz 讲的很清楚了，但感觉复杂度分析有点奇怪？很好奇 mrsrz 错误的块长是咋过的）。

设 $suf_{i,j}$ 表示第 $i$ 个数字与第 $i$ 个数字所对应的块后面的块一直到第 $j$ 个块的贡献，$pre_{i,j}$ 表示第 $i$ 个数字所对应的块后面的块一直到第 $j$ 个块的贡献，$F_{i,j}$ 表示第 $i$ 个块到第 $j$ 个块的答案。

显然最小值一定是权值 $a_i$ 相邻的两个数之间所取得，所以可以考虑先对于每个块按照权值从小到大排一遍序，然后暴力枚举每一个位置作为 $a_i$，然后双指针枚 $j$，使得 $a_i<a_j$，那么以 $a_i$ 更新位置 $j$ 所在块的 $suf_i$。

然后 $suf_{i,j}$ 显然是可以从 $suf_{i,j-1}$ 或者是 $suf_{i+1,j}$ 继承来的，那么直接取个 $\min$ 即可。

然后 $pre$ 的预处理同理。

那么 $F$ 显然可以由 $pre$ 转移，$F_{i,j}=pre_{R_j,i}$，注意 $F_{i,j}$ 还可以从 $F_{i,j-1}$ 以及 $F_{j,j}$ 继承。

至此就可以在 $\mathcal O(\frac{n^2}{B})$ 的时间内预处理出 $F,pre,suf$。

查询的时候可以把散块暴力双指针扫描（还是利用答案一定是权值排序后相邻两个数间取得的性质），中间整块查询答案 $F_i,j$ 即可，两边散块到中间的答案直接查 $pre,suf$，具体细节详见代码，显然这部分的时间复杂度是 $\mathcal O(mB)$。

令块大小为 $B$，则总时间复杂度为 $\mathcal O(\frac{n^2}B+mB)$。

显然当 $B=\frac{n}{\sqrt m}\approx 182$ 时，总时间复杂度最优，为 $\mathcal O(n\sqrt m)$。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#pragma GCC optimize(2)
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10,M=N/185+5;
int n,m,S=185,a[N],L[M],R[M],F[M][M],suf[N][M],pre[N][M],tot;
#define abs(x) ((x)<0?-(x):(x))
#define P pair<int,int>
#define MP make_pair
#define fi first
#define se second
vector<P> b[M];
I void B(){
    RI i,j,k,t,X,sz;for(i=1;i<=n;i++) !((i-1)%S)&&(R[tot]=i-1,L[++tot]=i),b[tot].push_back(MP(a[i],i));R[tot]=n;
    for(memset(pre,63,sizeof(pre)),memset(suf,63,sizeof(suf)),i=1;i<=tot;i++) for(F[i][i]=2e9,sort(b[i].begin(),b[i].end()),j=1;j<b[i].size();j++) F[i][i]=min(F[i][i],abs(b[i][j].fi-b[i][j-1].fi));
    for(i=1;i<=tot;i++) for(j=i+1;j<=tot;j++){for(t=0,k=0,sz=b[i].size();k<sz;k++){W(t<b[j].size()&&b[j][t].fi<b[i][k].fi) t++;t>0&&(suf[b[i][k].se][j]=min(suf[b[i][k].se][j],abs(b[i][k].fi-b[j][t-1].fi))),t<b[j].size()&&(suf[b[i][k].se][j]=min(suf[b[i][k].se][j],abs(b[i][k].fi-b[j][t].fi)));}for(k=R[i]-1;k>=L[i];k--) suf[k][j]=min(suf[k][j],suf[k+1][j]);}//排过序后，双指针扫描预处理出 suf
    for(i=1;i<=tot;i++) for(j=i-1;j;j--){for(t=0,k=0,sz=b[i].size();k<sz;k++){W(t<b[j].size()&&b[j][t].fi<b[i][k].fi) t++;t>0&&(pre[b[i][k].se][j]=min(pre[b[i][k].se][j],abs(b[i][k].fi-b[j][t-1].fi))),t<b[j].size()&&(pre[b[i][k].se][j]=min(pre[b[i][k].se][j],abs(b[i][k].fi-b[j][t].fi)));}for(k=L[i]+1;k<=R[i];k++) pre[k][j]=min(pre[k][j],pre[k-1][j]);}
    for(i=1;i<=tot;i++) for(j=L[i];j<=R[i];j++){for(k=i+2;k<=tot;k++) suf[j][k]=min(suf[j][k],suf[j][k-1]);for(k=i-2;k>=1;k--) pre[j][k]=min(pre[j][k],pre[j][k+1]);}
    for(i=1;i<=tot;i++) for(j=i+1;j<=tot;j++) F[i][j]=min(pre[R[j]][i],min(F[i][j-1],F[j][j]));//整块答案更新
}
#define bl(x) ((x-1)/S+1)
vector<int> v,g;
I int Merge(CI L1,CI R1,CI L2,CI R2){//两个散块暴力双指针扫描
    RI i,j,X=2e9,sz,vs,gs;for(v.clear(),g.clear(),sz=b[bl(L1)].size(),i=0;i<sz;i++) if(L1<=b[bl(L1)][i].se&&b[bl(L1)][i].se<=R1) v.push_back(b[bl(L1)][i].fi);
    for(i=0,sz=b[bl(L2)].size();i<sz;i++) if(L2<=b[bl(L2)][i].se&&b[bl(L2)][i].se<=R2) g.push_back(b[bl(L2)][i].fi);
    for(j=i=0,vs=v.size(),gs=g.size();i<vs;i++){W(j<gs&&g[j]<v[i]) j++;j>0&&(X=min(X,abs(g[j-1]-v[i]))),j<g.size()&&(X=min(X,abs(g[j]-v[i])));}return X;
}
I int G(CI L,CI R){//单块内暴力
    RI i,j,X,sz=b[bl(L)].size();j=0;W(j<sz&&!(L<=b[bl(L)][j].se&&b[bl(L)][j].se<=R)) j++;
    for(X=2e9,i=j+1;i<sz;j=i,i=j+1){W(i<sz&&!(L<=b[bl(L)][i].se&&b[bl(L)][i].se<=R)) i++;i<sz&&(X=min(X,abs(b[bl(L)][i].fi-b[bl(L)][j].fi)));}return X;
}
I int Q(CI l,CI r){
    RI i,j,X;if(bl(l)==bl(r)) return G(l,r);
    return X=min(suf[l][bl(r)-1],pre[r][bl(l)+1]),bl(l)+1<=bl(r)-1&&(X=min(X,F[bl(l)+1][bl(r)-1])),X=min(X,min(G(l,R[bl(l)]),G(L[bl(r)],r))),min(X,Merge(l,R[bl(l)],L[bl(r)],r));
}
int main(){
    RI i,l,r;for(read(n),i=1;i<=n;i++) read(a[i]);for(B(),read(m),i=1;i<=m;i++) read(l,r),writeln(Q(l,r));return clear(),0;
}