CF765F Souvenirs
Description
题目链接：CF765F
给定一个长度为 n 的序列 a_i，有 m 个询问，每次询问给定 l,r，求对于 i,jin[l,r]，且满足 inot = j，a_i - a_j 的最小值。
1leq nleq 10^5,1leq mleq 3times 10^5,0leq a_ileq 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_ja_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(nsqrt m)。
Code
代码语言：javascript复制#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 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;
} 
