CF1793F Rebrending Sol

考试考了个差不多的题，用这道题的方法可以剪枝暴力过题。

但是考场上完全忘掉了这个 trick。

遂写一篇题解记录。

我们可以考虑一些暴力的做法。

比如说开一棵线段树，对于每一个节点，存它对应的区间内的所有元素。

把每一个节点存的所有元素排序，那么询问的时候查询该元素的前驱后继即可。

但是这样做的复杂度显然很错。

考虑把询问离线下来，按照右端点排序。

整个过程是动态的，相当于每一次加入 \(a_i\)，然后与 \(a_{1 \cdots i-1}\) 合并答案。

合并答案只需要找前驱后继即可更新最小差。

但是这样还是很暴力，怎么办？可以剪枝啊。

对于当前需要更新的区间 \([l,r]\)，设中点 \(m\)。

那么先遍历 \((m,r]\)，再遍历 \([l,m]\)。

在遍历 \([l,m]\) 时如果答案直接不优，那么就跳出循环。

因为我们是按照右端点从小到大排序进行计算的，所以左端的答案只会被右端的答案替代。即，如果答案同样优秀，那么优先考虑右侧，因为后续还会用到这部分的值。

否则，如果先更新左侧，右侧被剪枝，后续如果要用到右侧的值就会直接导致错误。

没了，复杂度目测 \(\mathcal{O}(m \log^2 n)\)。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
using namespace std;

const int N = 3e5 + 10, inf = 1e18;
int n, q, curv, a[N], val[N << 2], res[N << 2];
vector <int> t[N << 2];
struct Node {
    int id, l, r;
    inline bool operator <(const Node &X) const {
        return r < X.r;
    }
} qry[N << 2];

inline void build(int rt, int l, int r) {
    val[rt] = inf;
    if (l == r) return t[rt].push_back(a[l]), void();
    int mid = (l + r) >> 1; build(ls, l, mid), build(rs, mid + 1, r);
    for (auto x: t[ls]) t[rt].push_back(x);
    for (auto x: t[rs]) t[rt].push_back(x);
    sort(t[rt].begin(), t[rt].end()); return ;
}

inline void upd(int rt, int l, int r, int pos, int vl) {
    if (r <= pos) {
        auto cur = lower_bound(t[rt].begin(), t[rt].end(), vl);
        if (cur != t[rt].begin()) val[rt] = min(val[rt], vl - *(cur - 1));
        if (cur != t[rt].end()) val[rt] = min(val[rt], *cur - vl);
        if (val[rt] >= curv) return ;
    }
    if (l < r) {
        int mid = (l + r) >> 1;
        if (pos > mid) upd(rs, mid + 1, r, pos, vl);
        upd(ls, l, mid, pos, vl), val[rt] = min(val[ls], val[rs]);
    }
    return curv = min(curv, val[rt]), void();
}

inline int query(int rt, int l, int r, int pos) {
    if (l >= pos) return val[rt]; int mid = (l + r) >> 1;
    if (pos > mid) return query(rs, mid + 1, r, pos);
    return min(val[rs], query(ls, l, mid, pos));
}

template <typename T> inline void read(T &x) {
    x = 0; char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
}

int main() {
    read(n), read(q); for (int i = 1; i <= n; ++i) read(a[i]);
    for (int i = 1; i <= q; ++i) read(qry[qry[i].id = i].l), read(qry[i].r);
    build(1, 1, n); sort(qry + 1, qry + 1 + q); int d = 1;
    for (int i = 2; i <= n; ++i) {
        curv = inf, upd(1, 1, n, i - 1, a[i]);
        while (qry[d].r == i) res[qry[d++].id] = query(1, 1, n, qry[d].l);
    }
    for (int i = 1; i <= q; ++i) printf("%d\n", res[i]);
    return 0;
}