CF765F Souvenirs 题解

Preface

在会压位 Trie 的前提下，本题最好想的做法应该是压位 Trie+回滚莫队，可是竟然没人写这个做法的题解？

Solution

我们先转化题意：设 \(a_i\) 在 \([l,r]\) 中的前驱后继分别为 \(s_i,p_i\)，对于每次询问，求 \(\min_{\forall i \in [l,r]}\min(s_i - a_i,p_i - a_i)\)。

静态查询让我们联想到莫队，求 \(\min\) 让我们联想到回滚莫队，求前驱后继让我们联想到 set。

此时我们获得了一个 \(O(n\sqrt n\log n)\) 的做法，但是显然通过不了 \(10^5\) 的数据。

此时想到压位 Trie 是可以在 \(O(\log_w V)\) 的时间复杂度解决 Dynamic Predecessor Problem 的，那么将 set 替换成压位 Trie，时间复杂度变为 \(O(n\sqrt n\log_w V)\)。

虽然上述做法的时间复杂度理论上可以通过，但是常数太大，交上去后显示 Time limit exceeded on test 16。

我们再进行一个优化：因为求前驱后继只是比较大小关系，所以我们可以对值域进行离散化，在计算 \(\min\) 时再替换回原来的 \(a_i\)。

时间复杂度：\(O(n\sqrt n\log_w n)\)。

虽然能过，但是时间复杂度还是被 2log 和分块做法吊打。/kk

Code

卡了个神奇块长。

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
//#define int long long
namespace IO
{
    inline int read()
    {
        int x = 0, f = 1;
        char ch = getchar();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x * f;
    }
    template <typename T> inline void print(T x)
    {
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) print(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;
const int N = 1e5 + 5;
typedef unsigned long long ull;
const int g = 6;
const int mod = (1 << g) - 1;
ull BUFF[1 << 25], *BT = BUFF + sizeof(BUFF) / sizeof(ull);
ull *alloc(int sz) {return BT -= sz;}
int dep;
ull *a[5];
void trie(int sz)
{
    dep = 1;
    int cnt;
    for ( ; ; dep++)
    {
        cnt = (sz + (1ull << g * dep) - 1) >> g * dep;
        a[dep - 1] = alloc(cnt);
        if (cnt == 1) return ;
    }
}
void insert(int x)
{ 
    for (int i = 0; i < dep; i++)
    {
        ull p = 1ull << (x >> i * g & mod);
        if (a[i][x >> (i + 1) * g] & p) return ;
        a[i][x >> (i + 1) * g] |= p;
    } 
}
void erase(int x)
{
    for (int i = 0; i < dep; i++)
        if (a[i][x >> (i + 1) * g] &= ~(1ull << (x >> i * g & mod))) return ;
}
int fdsuf(int x)
{
    for (int i = 0; i < dep; i++)
    {
        int cur = (x >> i * g) & mod;
        ull v = a[i][x >> (i + 1) * g];
        if (v >> cur > 1)
        {
            int res = x >> (i + 1) * g << (i + 1) * g;
            res += (__builtin_ctzll(v >> (cur + 1)) + cur + 1) << i * g;
            for (int j = i - 1; ~j; j--) 
                res += __builtin_ctzll(a[j][res >> (j + 1) * g]) << j * g;
            return res;
        }
    }
    return -1;
}
int fdpre(int x)
{
    for (int i = 0; i < dep; i++)
    {
        int cur = (x >> i * g) & mod;
        ull v = a[i][x >> (i + 1) * g];
        if (v & ((1ull << cur) - 1))
        {
            int res = x >> (i + 1) * g << (i + 1) * g;
            res += (mod - __builtin_clzll(v & ((1ull << cur) - 1))) << i * g;
            for (int j = i - 1; ~j; j--) 
                res += (mod - __builtin_clzll(a[j][res >> (j + 1) * g])) << j * g;
            return res;
        }
    }
    return -1;
}
int n, m, tmp, sq, mp[N], va[N], lsh[N], b[N], bel[N], ans[N * 3], c[N], mn = 1e9;
struct block
{
    int l, r, id;
    bool operator < (block x) const
    {
        if (bel[x.l] == bel[l]) return r < x.r;
        return l < x.l;
    } 
}q[N * 3];
void upmin(int &x, int y) {x = (x > y ? y : x);}
void add(int p) 
{
    int x = va[p], y = b[p];
    int suf = fdsuf(y), pre = fdpre(y);
    if (suf != -1) suf = va[c[suf]];
    if (pre != -1) pre = va[c[pre]];
    if (mp[y]) suf = pre = x;
    if (suf != -1) upmin(mn, suf - x);
    if (pre != -1) upmin(mn, x - pre);
    if (!mp[y]++) insert(y);
}
void del(int p) {if (!--mp[b[p]]) erase(b[p]);}
signed main()
{
    n = read();
    for (int i = 1; i <= n; i++) lsh[i] = b[i] = va[i] = read();
    sort(lsh + 1, lsh + n + 1);
    tmp = unique(lsh + 1, lsh + n + 1) - lsh - 1;
    m = read(), sq = n / sqrt(m * 3.5 / 6);
    for (int i = 1; i <= n; i++) 
    {
        int tm = lower_bound(lsh + 1, lsh + tmp + 1, b[i]) - lsh;
        c[tm] = i, b[i] = tm, bel[i] = (i - 1) / sq + 1;
    }
    trie(1 << 18);
    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);
    int l = 1, r = 0, lst;
    for (int i = 1; i <= m; i++)
    {
        int nl = min(bel[q[i].l] * sq, n);
        if (bel[q[i].l] != bel[q[i - 1].l]) 
        {
            while (l <= r) del(l++);
            l = nl, r = nl - 1, mn = 1e9;
        }
        l = nl;
        if (bel[q[i].l] == bel[q[i].r + 1])
        {
            nl = q[i].r + 1, l = nl, r = nl - 1, mn = 1e9;
            while (l > q[i].l) add(--l);
            while (l < nl) del(l++);
            ans[q[i].id] = mn, mn = 1e9;
            continue;
        }
        if (r < l - 1) r = l - 1; 
        while (r < q[i].r) add(++r);
        lst = mn;
        while (l > q[i].l) add(--l);
        while (l < nl) del(l++);
        ans[q[i].id] = mn, mn = lst;
    }
    for (int i = 1; i <= m; i++) print(ans[i]), puts("");
    return 0;
}