[笔记]基础离线算法

joyslog · 2022-12-12 22:17:00 · 个人记录

\text{Updated on 12/16/2022}

Better Reading Experience

怎么说呢，上周五斟酌了一下，报了某谷的省选计划听听看。第一节说是讲了一些很基础的东西，但是我很多算法都没有学过阿！！果然我还是太菜了吗呜呜呜，感觉又回到刚开始学 OI 的时候大家都认为很基础的东西但我都不会那种奇特的感觉qwq。

另外，这节课讲的东西很杂。非要我能分类出一个专题来的话就是讲了两个离线算法就是 CDQ分治 和 整体二分。正好之前没学过，所以来写个笔记。

另外放了两题也是需要离线做的可爱题。

毕竟刚学这两玩意，所有写过的这两个算法的题都在这下面了，这篇文章肯定非常非常不能够说明这两个算法的各种用途，大概之后会记得补上！！

CDQ 分治

oi-wiki 上介绍 CDQ 分治可以解决的三类问题：

解决和点对有关的问题。
1D 动态规划的优化与转移。
通过 CDQ 分治，将一些动态问题转化为静态问题。

这里暂时不提到优化动态规划这部分，因为我不会。之后再补。

三维偏序

洛谷 P3810

有 n 个元素，第 i 个元素有 a_i,b_i,c_i 三个属性，设 f(i) 表示满足 a_j \leq a_i 且 b_j \leq b_i 且 c_j \leq c_i 且 j \ne i 的 j 的数量。

对于 d \in [0, n) ，求 f(i) = d 的数量。

考虑 CDQ 分治：

我们先把元素按 a_i 排序并对属性去重。

把区间分为 [l,mid] 与 [mid + 1,r]，由于已经排序，则从左右两个区间分别任选出两个元素自然会满足 a_i\leq a_j。

然后对于 b_i 的要求，用类似归并排序来统计。

对于 c_i 的要求，用树状数组来统计。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct node {int a, b, c, cnt, ans;} a[MAX_N], q[MAX_N];
int ans[MAX_N];
bool cmpb(node x, node y) {
    if(x.b == y.b)  return x.c < y.c;
    return x.b < y.b;
}
bool cmpa(node x, node y) {
    if(x.a == y.a)  return cmpb(x, y);
    return x.a < y.a;
}
int lowbit(int x) {return x & -x;}
struct treearray {
    int t[MAX_N], len;
    treearray() {memset(t, 0, sizeof(t));}
    void add(int pos, int x) {
        for(int i = pos; i <= len; i += lowbit(i))
            t[i] += x;
    }
    int query(int pos) {
        int ans = 0;
        for(int i = pos; i >= 1; i -= lowbit(i))
            ans += t[i];
        return ans;
    }
} tree;

inline ll read() {...}
inline void write(ll x) {...}

void CDQ(int l, int r) {
    if(l == r)  return;
    int mid = (l + r) >> 1;
    CDQ(l, mid), CDQ(mid + 1, r);
    sort(q + l, q + mid + 1, cmpb), sort(q + mid + 1, q + r + 1, cmpb);
    int i = l, j = mid + 1;
    for(; j <= r; j++) {
        while(q[i].b <= q[j].b && i <= mid)
            tree.add(q[i].c, q[i].cnt), i++;
        q[j].ans += tree.query(q[j].c); 
    }
    for(int k = l; k < i; k++)
        tree.add(q[k].c, -q[k].cnt);
}

int main() {
    int n = read(), k = read(), cnt = 0, m = 0;
    tree.len = k;
    for(int i = 1; i <= n; i++)
        a[i].a = read(), a[i].b = read(), a[i].c = read();
    sort(a + 1, a + n + 1, cmpa);
    for(int i = 1; i <= n; i++) {
        cnt++;
        if(a[i].a != a[i + 1].a || a[i].b != a[i + 1].b || a[i].c != a[i + 1].c)
            q[++m] = a[i], q[m].cnt = cnt, cnt = 0;     
    }
    CDQ(1, m);
    for(int i = 1; i <= m; i++)
        ans[q[i].ans + q[i].cnt - 1] += q[i].cnt;
    for(int i = 0; i < n; i++)
        write(ans[i]), putchar('\n');
}

动态逆序对

洛谷 P3157

对于序列 a，它的逆序对数定义为集合

\{(i,j)| i<j \wedge a_i > a_j \}

中的元素个数。

现在给出 1\sim n 的一个排列，按照某种顺序依次删除 m 个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。

设 a_i 的删除时间为 tim_i，则逆序对只需要满足 i<j \wedge a_i > a_j \wedge tim_i < tim_j，所以转化为三维偏序。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
struct node {
    int val, tim, ans;
    node() {val = 0, tim = 0, ans = 0;}
} a[MAX_N];
int pos[MAX_N], n, m;
ll ans[MAX_N];
struct TreeArray {
    int t[MAX_N];
    int lowbit(int x) {return x & -x;}
    void add(int i, int x) {for(; i <= n + 1; i += lowbit(i))   t[i] += x;}
    ll query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i)) ret += t[i]; return ret;}
} tree;

inline ll read() {...}
char buf[100];
inline void write(ll x) {...}

inline bool cmpval(node x, node y) {return x.val < y.val;}
inline bool cmptim(node x, node y) {return x.tim < y.tim;}
// 原逆序对
ll solve() {
    ll ret = 0;
    for(int i = 1; i <= n; i++) {
        ret += tree.query(n + 1) -  tree.query(a[i].val);
        tree.add(a[i].val, 1);
    }
    for(int i = 1; i <= n; i++)
        tree.add(a[i].val, -1);
    return ret;
}

void CDQ(int l, int r) {
    if(l == r)  return;
    int mid = (l + r) >> 1;
    CDQ(l, mid), CDQ(mid + 1, r);
    int i = l, j = mid + 1;
    for(; i <= mid; i++) {
        while(j <= r && a[i].val > a[j].val)
            tree.add(a[j].tim, 1), j++;
        a[i].ans += tree.query(m + 1) - tree.query(a[i].tim);
    }
    for(int k = mid + 1; k < j; k++)
        tree.add(a[k].tim, -1);
    i = mid, j = r;
    for(; j >= mid + 1; j--) {
        while(i >= l && a[i].val > a[j].val)
            tree.add(a[i].tim, 1), i--;
        a[j].ans += tree.query(m + 1) - tree.query(a[j].tim);
    }
    for(int k = mid; k > i; k--)
        tree.add(a[k].tim, -1);
    sort(a + l, a + r + 1, cmpval);
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        a[i].val = read();
        pos[a[i].val] = i;
    }
    for(int i = 1; i <= m; i++) {
        int x = read();
        a[pos[x]].tim = i;
    }
    for(int i = 1; i <= n; i++)
        if(!a[i].tim)   a[i].tim = m + 1;
    ll old = solve();
    CDQ(1, n);
    sort(a + 1, a + n + 1, cmptim);
    for(int i = 1; i <= m; i++) {
        write(old), putchar('\n');
        old -= a[i].ans; 
    }
    return 0;
}

整体二分

如果一个问题可以二分答案、且有多组询问、可离线，那么有时候可以将所有的询问一起二分。

具体做法是，猜测答案值域的 mid 是定义域内所有问题的答案，并将询问依据它的答案与 mid 的关系分成两部分进行分治。整体二分的复杂度是 O(Q \log V)，其中 V 是二分答案的值域。有时候要套数据结构。

区间静态第 k 小

洛谷 P3834

我们先离散化，然后把数列的数值也加到询问数组里，方便遍历分治的区间内对询问有影响的数值，打个 type 标记区分是询问还是数值即可。

每次猜测在当前分治的 [ql,qr] 内询问的所有答案都为 mid，然后遍历一遍 [ql,qr] 内的所有询问。

如果遇到一个数值 a_i 且 a_i \le mid，把它的位置加入树状数组，并把它分到分治的左半部分；否则分到右半部分。
如果遇到一个询问 (L,R)，用树状数组查询当前 [L,R] 内有多少个数，记为 x。如果 x\le k，把这个询问分到分治的左半部分；否则分到右半部分。

当前这一层执行完后，我们把树状数组清空，递归下去分治即可。

像二分一样，当答案的值域 [l,r] 內只有一个元素时 (l==r)，递归结束，当前询问区间 [ql,qr] 内的询问答案即为 l。

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2e5 + 10;
typedef long long ll;
typedef pair<int, int> pii;
struct que {
    int l, r, k, id, type;
    que(int _l = 0, int _r = 0, int _k = 0, int _id = 0, int _type = 0) : l(_l), r(_r), k(_k), id(_id), type(_type){}
};
int n, m, tot, cnt;
pii raw[MAX_N];
int a[MAX_N], val[MAX_N], ans[MAX_N];
que q[MAX_N << 1], q1[MAX_N << 1], q2[MAX_N << 1];

struct TreeArray {
    int t[MAX_N];
    TreeArray() {memset(t, 0, sizeof(t));}
    int lowbit(int x) {return x & -x;}
    void add(int i, int v) {for(; i <= n; i += lowbit(i))   t[i] += v;}
    int query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i))    ret += t[i]; return ret;}
} tree;

inline ll read() {...}
char buf[50];
inline void write(ll x) {...}

void solve(int l, int r, int ql, int qr) {
    if(ql > qr) return;
    if(l == r) {
        for(int i = ql; i <= qr; i++)
            if(q[i].type == 2)  ans[q[i].id] = l;
        return;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
    for(int i = ql; i <= qr; i++) {
        if(q[i].type == 1) {
            if(q[i].l <= mid)   tree.add(q[i].id, 1), q1[++cnt1] = q[i];
            else    q2[++cnt2] = q[i];
        } 
        else {
            int x = tree.query(q[i].r) - tree.query(q[i].l - 1);
            if(q[i].k <= x) q1[++cnt1] = q[i];
            else    q[i].k -= x, q2[++cnt2] = q[i];
        }
    }
    for(int i = 1; i <= cnt1; i++)
        if(q1[i].type == 1) tree.add(q1[i].id, -1);
    for(int i = 1; i <= cnt1; i++)
        q[i + ql - 1] = q1[i];
    for(int i = 1; i <= cnt2; i++)
        q[i + cnt1 + ql - 1] = q2[i];
    solve(l, mid, ql, cnt1 + ql - 1);
    solve(mid + 1, r, ql + cnt1, qr);

}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        raw[i].first = read(), raw[i].second = i;
    sort(raw + 1, raw + n + 1);
    for(int i = 1; i <= n; i++) {
        if(raw[i] != raw[i - 1])    tot++;
        a[raw[i].second] = tot;
        val[tot] = raw[i].first;        
    }
    for(int i = 1; i <= n; i++)
        q[++cnt] = que(a[i], -1, -1, i, 1);
    for(int i = 1; i <= m; i++)
        q[++cnt].l = read(), q[cnt].r = read(), q[cnt].k = read(), q[cnt].id = i, q[cnt].type = 2;
    solve(0, tot + 1, 1, cnt);
    for(int i = 1; i <= m; i++)
        write(val[ans[i]]), putchar('\n');
    return 0;
}

[例题] MET-Meteors

洛谷 P3527

有 n 个成员国。现在它发现了一颗新的星球，这颗星球的轨道被分为 m 份（第 m 份和第 1 份相邻），第 i 份上有第 a_i 个国家的太空站。

这个星球经常会下陨石雨。BIU 已经预测了接下来 k 场陨石雨的情况。

BIU 的第 i 个成员国希望能够收集 p_i 单位的陨石样本。你的任务是判断对于每个国家，它需要在第几次陨石雨之后，才能收集足够的陨石。

对于这题，我们像上面一样进行分治。每次把 [l,mid] 的陨石雨下下来，用树状数组维护每个位置接受到的陨石，然后枚举当前询问区间 [ql,qr]，用树状数组查询每个国家现在接受到了多少陨石。如果接受到的量小于期望，分到左边；否则分到右边。

细节略多，调了很久。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 6e5 + 10;
ll n, m, k;
struct TreeArray {
    ll t[MAX_N];
    TreeArray() {memset(t, 0, sizeof(t));}
    int lowbit(int x) {return x & -x;}
    void add(int i, ll v) {for(; i <= 2 * m; i += lowbit(i))    t[i] += v;}
    ll query(int i) {ll ret = 0; for(; i >= 1; i -= lowbit(i))  ret += t[i]; return ret;}
} tree;
struct que {
    ll pos, need, ans;
    bool operator < (const que &t) const {return pos < t.pos;}
} q[MAX_N], q1[MAX_N], q2[MAX_N];
struct op {ll l, r, val;} ops[MAX_N];
vector<ll> bl[MAX_N];

inline ll read() {...}
inline void write(ll x) {...}

void solve(int l, int r, int ql, int qr) {
    if(ql > qr) return;
    if(l == r) {
        for(int i = ql; i <= qr; i++)
            q[i].ans = l;
        return;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
    for(int i = l; i <= mid; i++)
        tree.add(ops[i].l, ops[i].val), tree.add(ops[i].r + 1, -ops[i].val);
    for(int i = ql; i <= qr; i++) {
        ll sum = 0;
        for(ll j : bl[q[i].pos]) {
            sum += tree.query(j), sum += tree.query(j + m);
            if(sum > q[i].need) break;
        }
        if(q[i].need <= sum)  q1[++cnt1] = q[i];
        else    q[i].need -= sum, q2[++cnt2] = q[i];
    }
    for(int i = l; i <= mid; i++)
        tree.add(ops[i].l, -ops[i].val), tree.add(ops[i].r + 1, ops[i].val);
    for(int i = 1; i <= cnt1; i++)
        q[i + ql - 1] = q1[i];
    for(int i = 1; i <= cnt2; i++)
        q[i + ql + cnt1 - 1] = q2[i];
    solve(l, mid, ql, ql + cnt1 - 1);
    solve(mid + 1, r, ql + cnt1, qr);
} 

int main() {
    n = read(), m = read();
    for(int i = 1; i <= m; i++)
        bl[read()].push_back(i);
    for(int i = 1; i <= n; i++)
        q[i].need = read(), q[i].pos = i;
    k = read();
    for(int i = 1; i <= k; i++) {
        ops[i].l = read(), ops[i].r = read(), ops[i].val = read();
        if(ops[i].r < ops[i].l) ops[i].r += m;
    }
    solve(1, k + 1, 1, n);
    sort(q + 1, q + n + 1);
    for(int i = 1; i <= n; i++) {
        if(q[i].ans == k + 1)   puts("NIE");
        else    write(q[i].ans), putchar('\n');
    }
    return 0;
}

带修区间第 k 小

洛谷 P2617

基本就是静态区间第 k 小，把修改操作分割成了删除原数 \to 插入新数的形式即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5 + 10;
int n, m;
struct op {
    int x, y, k, type, id;
    op(int _x = 0, int _y = 0, int _k = 0, int _type = 0, int _id = 0) : x(_x), y(_y), k(_k), type(_type), id(_id) {}
} q[MAX_N << 2], q1[MAX_N << 2], q2[MAX_N << 2];
struct TreeArray {
    int t[MAX_N];
    TreeArray() {memset(t, 0, sizeof(t));}
    int lowbit(int x) {return x & -x;}
    void add(int i, int x) {for(; i <= n; i += lowbit(i))   t[i] += x;}
    int query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i))    ret += t[i]; return ret;}
} tree;
int tot, a[MAX_N], ans[MAX_N];

inline ll read() {...}
inline void write(ll x) {...}
inline char read_char() {...}

void solve(int l, int r, int ql, int qr) {
    if(l > r || ql > qr) return;
    if(l == r) {
        for(int i = ql; i <= qr; i++)
            if(q[i].type == 1)  ans[q[i].id] = l;
        return;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
    for(int i = ql; i <= qr; i++) {
        if(q[i].type == 0) {
            if(q[i].y <= mid)   tree.add(q[i].x, q[i].k), q1[++cnt1] = q[i];
            else    q2[++cnt2] = q[i];
        }
        else {
            int t = tree.query(q[i].y) - tree.query(q[i].x - 1);
            if(q[i].k <= t) q1[++cnt1] = q[i];
            else    q[i].k -= t, q2[++cnt2] = q[i];
        }
    }
    for(int i = 1; i <= cnt1; i++) {
        q[ql + i - 1] = q1[i];
        if(q1[i].type == 0) tree.add(q1[i].x, -q1[i].k);
    }
    for(int i = 1; i <= cnt2; i++)
        q[ql + i + cnt1 - 1] = q2[i];
    solve(l, mid, ql, ql + cnt1 - 1);
    solve(mid + 1, r, ql + cnt1, qr);
}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++) {
        a[i] = read();
        q[++tot] = op(i, a[i], 1, 0, -1);
    }
    for(int i = 1; i <= m; i++) {
        char opt = read_char();
        ans[i] = -1;
        if(opt == 'Q') {
            int x = read(), y = read(), k = read();
            q[++tot] = op(x, y, k, 1, i);
        }
        else {
            int x = read(), y = read();
            q[++tot] = op(x, a[x], -1, 0, -1);
            a[x] = y;
            q[++tot] = op(x, a[x], 1, 0, -1);
        }
    }
    solve(0, 1e9, 1, tot);
    for(int i = 1; i <= m; i++)
        if(ans[i] != -1)    write(ans[i]), putchar('\n');
    return 0;
}

二维矩阵询问子矩阵第 k 小

洛谷 P1527

思路和一维的情况类似，把树状数组换成二维树状数组即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 610, MAX_Q = 6e4 + 10;
int n, q, tot, tmp;
int ans[MAX_Q];
struct node {
    int x, y, val;
    bool operator < (const node &t) const {return val < t.val;}
    node(int _x = 0, int _y = 0, int _val = 0) : x(_x), y(_y), val(_val) {}
} a[MAX_N * MAX_N];
struct que {
    int x, y, X, Y, k, id;
    que(int _x = 0, int _y = 0, int _X = 0, int _Y = 0, int _k = 0, int _id = 0) : x(_x), y(_y), X(_X), Y(_Y), k(_k), id(_id) {}
} qs[MAX_Q], q1[MAX_Q], q2[MAX_Q];
struct TreeArray {
    int t[MAX_N][MAX_N];
    TreeArray() {memset(t, 0, sizeof(t));}
    int lowbit(int x) {return x & -x;}
    void add(int x, int y, int v) {
        for(int i = x; i <= n; i += lowbit(i))
            for(int j = y; j <= n; j += lowbit(j))
                t[i][j] += v;
    }
    int query(int x, int y) {
        int ret = 0;
        for(int i = x; i >= 1; i -= lowbit(i))
            for(int j = y; j >= 1; j -= lowbit(j))
                ret += t[i][j];
        return ret;
    }
    int sum(que p) {return query(p.X, p.Y) - query(p.x - 1, p.Y) - query(p.X, p.y - 1) + query(p.x - 1, p.y - 1);}
} tree;

inline ll read() {...}
inline void write(ll x) {...}

void solve(int l, int r, int ql, int qr) {
    if(ql > qr) return;
    if(l == r) {
        for(int i = ql; i <= qr; i++)
            ans[qs[i].id] = a[l].val;
        return;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0;
    for(int i = l; i <= mid; i++)
        tree.add(a[i].x, a[i].y, 1);
    for(int i = ql; i <= qr; i++) {
        int t = tree.sum(qs[i]);
        if(qs[i].k <= t)    q1[++cnt1] = qs[i];
        else    qs[i].k -= t, q2[++cnt2] = qs[i];
    }
    for(int i = l; i <= mid; i++)
        tree.add(a[i].x, a[i].y, -1);
    for(int i = 1; i <= cnt1; i++)
        qs[ql + i - 1] = q1[i];
    for(int i = 1; i <= cnt2; i++)
        qs[ql + cnt1 + i - 1] = q2[i];
    solve(l, mid, ql, ql + cnt1 - 1);
    solve(mid + 1, r, ql + cnt1, qr);
}

int main() {
    n = read(), q = read();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            tmp = read(), a[++tot] = node(i, j, tmp);
    for(int i = 1; i <= q; i++) {
        int x = read(), y = read(), X = read(), Y = read(), k = read();
        qs[i] = que(x, y, X, Y, k, i);
    }
    sort(a + 1, a + tot + 1);
    solve(1, n * n, 1, q);
    for(int i = 1; i <= q; i++)
        write(ans[i]), putchar('\n');
    return 0;
}

二维数点

模板题

给定平面上的 n 个点的坐标 (x_i,y_i)。

有 Q 次询问，每次给出 x_1, y_1, x_2, y_2，要求求出以 (x_1,y_1) 为左下角， (x_2,y_2) 为右上角的矩形范围内的点的个数。

题解

数据范围让我们不能直接用前缀和解决，但我们可以用前缀和的思想。考虑用 f(u,v) 表示 (0,0) 到 (u,v) 内的点数，则一个询问 (x_1, y_1, x_2, y_2) 可以拆成 f(x_2, y_2) - f(x_1 - 1,y_2) - f(x_2, y_1 - 1) + f(x_1 -1, y_1 - 1)。

那么可以把询问离线下来，按 x 排序，用树状数组来维护 y 这一维上点的个数。

具体来说，对于我们拆出来的单个询问 f(u,v)，我们直接把所有 x_i\le u 的点的 y_i 在树状数组里 +1，然后用 v 查询树状数组的前缀和即为 f(u,v)。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_RANGE = 1e7 + 10, MAX_N = 5e5 + 10;
int n, m, tot, now = 1;
struct TreeArray {
    int t[MAX_RANGE];
    TreeArray() {memset(t, 0, sizeof(t));}
    inline int lowbit(int x) {return x & -x;}
    inline void add(int i, int v) {for(; i <= n; i += lowbit(i))   t[i] += v;}
    inline int query(int i) {int ret = 0; for(; i >= 1; i -= lowbit(i))    ret += t[i]; return ret;}
} tree;
struct que {
    int x, y, sgn, id;
    que(int _x = 0, int _y = 0, int _sgn = 0, int _id = 0) : x(_x), y(_y), sgn(_sgn), id(_id) {}
    bool operator < (const que &t) const {return x == t.x ? y < t.y : x < t.x;}
} q[MAX_N << 2];
pii pts[MAX_N];
int ans[MAX_N];

inline ll read() {...}
inline void write(ll x) {...}

int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        pts[i].first = read() + 1, pts[i].second = read() + 1;
    sort(pts + 1, pts + n + 1);
    for(int i = 1; i <= m; i++) {
        int x = read() + 1, y = read() + 1, X = read() + 1, Y = read() + 1;
        q[++tot] = que(X, Y, 1, i);
        q[++tot] = que(x - 1, Y, -1, i);
        q[++tot] = que(X, y - 1, -1, i);
        q[++tot] = que(x - 1, y - 1, 1, i);
    }
    sort(q + 1, q + tot + 1);
    for(int i = 1; i <= tot; i++) {
        while(now <= n && pts[now].first <= q[i].x)
            tree.add(pts[now].second, 1), now++;
        ans[q[i].id] += q[i].sgn * tree.query(q[i].y);
    }
    for(int i = 1; i <= m; i++)
        write(ans[i]), putchar('\n');
    return 0;
}

宝石之国

校内模拟赛的一题，不知道出处挂不了链接，可以自己查一下哪里可以提交

给定一个 n 个数的数列 a_1,a_2,\dots , a_n，有 m 次询问，每次给出两个端点 l,r，询问区间 [l,r] 内两个相同元素的最短距离。对于 a_x=a_y，它们的距离定义为 |x-y|。

如果区间内不存在相同元素，输出 -1。

n,m\le2\times 10^5

题解

把所有询问离线下来，按右端点排序。每次把 pos\le q_i.r 的点纳入考虑范围内，即把距离更新到线段树的上一个位置处，然后用线段树维护区间最小值即可。

离散化一下比较好，因为这题没给 a_i 的范围。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2e5 + 10, INF = (1 << 30);
int a[MAX_N], t[MAX_N], lstpos[MAX_N];
struct que {
    int l, r, id, ans;
    bool operator < (const que &t) const {return r < t.r;}
} q[MAX_N];
bool cmpid(que x, que y) {return x.id < y.id;}
int d[MAX_N << 2];
inline ll read() {...}
char buf[100];
inline void write(ll x) {...}

inline int lc(int p) {return (p << 1);}
inline int rc(int p) {return (p << 1) | 1;}
inline int mid(int s, int t) {return (s + ((t - s) >> 1));}
inline void pu(int p) {d[p] = min(d[lc(p)], d[rc(p)]);}
void build_tree(int s, int t, int p) {
    if(s == t) {
        d[p] = INF;
        return;
    }
    int m = mid(s, t);
    build_tree(s, m, lc(p));
    build_tree(m + 1, t, rc(p));
    pu(p);
}
void update(int s, int t, int p, int x, int v) {
    if(s == t) {
        d[p] = v;
        return;
    }
    int m = mid(s, t);
    if(x <= m)  update(s, m, lc(p), x, v);
    else    update(m + 1, t, rc(p), x, v);
    pu(p);
}
int query(int s, int t, int p, int l, int r) {
    if(l <= s && t <= r)    return d[p];
    int m = mid(s, t), ret = INF;
    if(l <= m)  ret = min(ret, query(s, m, lc(p), l, r));
    if(r > m)   ret = min(ret, query(m + 1, t, rc(p), l, r));
    return ret;
}

int main() {
    int n = read(), m = read();
    for(int i = 1; i <= n; i++) 
        t[i] = a[i] = read();
    sort(t + 1, t + n + 1);
    int tot = unique(t + 1, t + n + 1) - t - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(t + 1, t + tot + 1, a[i]) - t;
    for(int i = 1; i <= m; i++) {
        q[i].l = read(), q[i].r = read();
        q[i].id = i;
    }
    sort(q + 1, q + m + 1);
    build_tree(1, n, 1);
    int now = 1;
    for(int i = 1; i <= m; i++) {
        while(now <= q[i].r) {
            if(lstpos[a[now]])  update(1, n, 1, lstpos[a[now]], now - lstpos[a[now]]);
            lstpos[a[now]] = now;
            now++;
        }
        q[i].ans = query(1, n, 1, q[i].l, q[i].r);
        if(q[i].ans == INF) q[i].ans = -1;
    }
    sort(q + 1, q + m + 1, cmpid);
    for(int i = 1; i <= m; i++)
        write(q[i].ans), putchar('\n');
    return 0;
}