CF765F Souvenirs

· · 题解

CF765F Souvenirs

可以发现这个问题类似询问区间逆序对（都和排序相关，都和点对相关），于是我们可以顺着 P5046 的方法去想。

分块。把询问分成询问端点同块与询问端点异块的情况。

询问端点同块

此时可以考虑处理出每个块排序后的数组。沿着排序后的数组，按大小顺序地“取出”l\sim r 的这一段区间，然后统计。

询问端点异块

参照 P5046 分成如下几部分：

  1. 散块内部与散块之间
  2. 整块与散块之间
  3. 整块内部与整块之间

散块内部与散块之间

与询问端点同块情况类似，取出两个散块分别得排序后的状态，归并起来，然后统计，我直接用了 STL。

整块与散块之间

预处理两个数组：

那如何预处理呢？可以考虑先处理 一个位置对一个块的答案，再前缀和变成 一个前缀/后缀对一个块的答案，再前缀和成 一个前缀/后缀对一些块的答案。

那 一个位置对一个块的答案 怎么算呢？可以先钦定两个块 a,b，然后用双指针算块 a 内的所有数分别与块 b 的答案。

具体算法为：块 a 内的元素从小往大算（别忘了我们之前给每个块排过序），然后定义一个指针 p，p 一开始位于 b 的块首，然后随着 a 内计算的位置从前往后，p 也随着变大，期间满足排序后的数组内 a_p<a_i。

这两个数组没有相交的地方，考虑将其合并。

整块内部与整块之间

考虑预处理 S_{i,j} 代表块 i 开头至块 j 结尾之间的答案。

可以先处理 S_{i,i} 代表一个块的答案，然后利用 D 数组扩展到多个块的答案。

代码

感觉写的还算简单，100 行不到。

#include<stdio.h>
#include<math.h>
#include<algorithm>

const int SIZ = 1000000;

namespace IO{ // by OneZzz6174

using IO::read;
using IO::readc;
using IO::print;
using IO::flush;

#define rint register int
#define rep(i,a,b) for(rint i = (a);i <= (b);++i)
#define Rep(i,a,b) for(rint i = (a);i >= (b);--i)

inline int max2(rint a,rint b){ return a>b?a:b; }
inline int min2(rint a,rint b){ return a<b?a:b; }
inline int chkmax(rint &a,rint b){ return a=a>b?a:b; }
inline int chkmin(rint &a,rint b){ return a=a<b?a:b; }
inline int abs2(rint x){ return x>0?x:-x; }

const int maxn = 1e5 + 5;
const int sqr = 325;
const int inf = 1e9 + 5;

int n,m,a[maxn],B,C;
int D[maxn][sqr],S[sqr][sqr];
int st[sqr],ed[sqr],bl[maxn];
int tmp[maxn];

struct value{
    int i,x;
    bool operator<(const value& v) const {
        return x < v.x;
    }
} b[maxn];

int qry0(rint l,rint r){
    int ans = inf,len = 0;
    rep(i,st[bl[l]],ed[bl[l]])
        if(l <= b[i].i && b[i].i <= r) tmp[++len] = b[i].x;
    rep(i,2,len) chkmin(ans,tmp[i] - tmp[i - 1]);
    return ans;
}

int qry1(rint l1,rint r1,rint l2,rint r2){
    int len = 0,p = r1 - l1 + 1,ans = inf;
    rep(i,st[bl[l1]],ed[bl[l1]])
        if(l1 <= b[i].i && b[i].i <= r1) tmp[++len] = b[i].x;
    rep(i,st[bl[l2]],ed[bl[l2]])
        if(l2 <= b[i].i && b[i].i <= r2) tmp[++len] = b[i].x;
    std::inplace_merge(tmp + 1,tmp + p + 1,tmp + len + 1);
    rep(i,2,len) chkmin(ans,tmp[i] - tmp[i - 1]); 
    return ans;
}

void init(){
    B = sqrt(n); C  = (n - 1) / B + 1;
    rep(i,1,C){
        st[i] = (i - 1) * B + 1;
        ed[i] = i == C ? n : i * B;
        rep(j,st[i],ed[i]) bl[j] = i,b[j].i = j,b[j].x = a[j];
        std::sort(b + st[i],b + ed[i] + 1);
    }
    rep(i,1,C){
        rep(j,1,C) if(i ^ j){
            rint p = st[j];
            rep(k,st[i],ed[i]){
                while(p < ed[j] && b[p + 1].x < b[k].x) ++p;
                D[b[k].i][j] = abs2(b[k].x - b[p].x);
                if(p < ed[j]) chkmin(D[b[k].i][j],abs2(b[k].x - b[p + 1].x));
            }
        }
        rep(j,st[i],ed[i]) rep(k,i + 2,C) chkmin(D[j][k],D[j][k - 1]);
        rep(j,st[i],ed[i]) Rep(k,i - 2,0) chkmin(D[j][k],D[j][k + 1]);
        rep(k,1,i - 1) rep(j,st[i] + 1,ed[i]) chkmin(D[j][k],D[j - 1][k]);
        rep(k,i + 1,C) Rep(j,ed[i] - 1,st[i]) chkmin(D[j][k],D[j + 1][k]);
        S[i][i] = qry0(st[i],ed[i]);
    }
    rep(i,1,C) rep(j,i + 1,C) S[i][j] = min2(min2(S[i][j - 1],S[j][j]),D[ed[j]][i]);
}   

int qry(rint l,rint r){
    if(bl[l] == bl[r]) return qry0(l,r);
    int ans = qry1(l,ed[bl[l]],st[bl[r]],r);
    if(bl[l] + 1 <= bl[r] - 1){ 
        chkmin(ans,S[bl[l] + 1][bl[r] - 1]);
        chkmin(ans,min2(D[r][bl[l] + 1],D[l][bl[r] - 1]));
    }
    return ans;
}

int main(){
    read(n); rep(i,1,n) read(a[i]);
    init(); read(m);
    while(m--){
        int l,r; read(l,r);
        print(qry(l,r),'\n');
    }
    return flush(),0;
}