CF765F Souvenirs

LuoGu: CF765F Souvenirs

CF: F. Souvenirs

考虑离线，对于相同的 $r$ ，将询问放在一起，扫描线动态维护不同 $l$ 的答案。注意到，$l$ 处答案相当于从 $l$ 开始的到 $r$ 的一段后缀最小值，所以考虑用树状数组维护。绝对值不太好操作，考虑只考虑 $w _ l < w _ r$ 的情况，最后将 $w _ i$ 都在值域上翻转一次即可。

考虑暴力，在 $r$ 前面寻找所有满足 $w _ j > w _ i$ 的 $j$ ，然后将 $j$ 处的答案对 $w _ j - w _ r$ 取 $\min$ ，查询时查询后缀答案，这样最坏需要找 $O(n)$ 次。考虑此时取到了 $w _ j$ ，考虑下一个 $i$ 以更新 $i$ 前面的答案，在 $j$ 处时 $i$ 被更新过，即前面的最小值一定是小于等于 $\left | w _ i - w _ j \right |$ 的，考虑到这时处理 $w _ i > w _ r$ 的情况，如果 $w _ i > w _ j$ 显然 $w _ i - w _ r > w _ j - w _ r$ ，不如选择 $j$ 更优，那么如果要更新答案，一定要满足 $w _ i - w _ r < \left | w _ i - w _ j \right | = w _ j - w _ i$ ，即 $w _ i < \frac {w _ j + w _ r} 2$ ，考虑建立一个动态开点值域线段树，那么可以在 $\log w$ 的时间内查询到下一个可以更新的值，而可以更新答案的值域每次在减半，也就是最多查询 $\log w$ 次，那么整体的复杂度为 $O(n \log ^ 2 w)$ 。

查看代码

#include <cstdio>
#include <vector>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
template <class Type>
void chkmin (Type &x, Type k)
{
    k < x && (x = k);
}
template <class Type>
void chkmax (Type &x, Type k)
{
    (x < k) && (x = k);
}
const int N = 1e5 + 10, Q = 3e5 + 10, inf = 1e9;
int n, m, w[N], ans[Q];
struct Query
{
    int l, id;
};
vector <Query> q[N];
namespace BIT
{
    int tr[N];
    void init()
    {
        for (int i = 1; i <= n; i++)
            tr[i] = inf;
    }
    void modify (int x, int k)
    {
        for (; x; x -= x & -x)
            chkmin(tr[x], k);
    }
    int query (int x)
    {
        int res = inf;
        for (; x <= n; x += x & -x)
            chkmin(res, tr[x]);
        return res;
    }
}
namespace PresidentTree
{
    const int M = 9e6 + 10;
    struct Node
    {
        int l, r, v;
    } tr[M];
    int rt, idx;
    void init()
    {
        for (int i = 1; i <= idx; i++)
            tr[i].l = tr[i].r = tr[i].v = 0;
        rt = idx = 0;
    }
    void modify (int &x, int t, int k, int l = 0, int r = inf)
    {
        !x && (x = ++idx);
        chkmax(tr[x].v, k);
        if (l == r)
            return;
        int mid = l + r >> 1;
        t <= mid ? modify(tr[x].l, t, k, l, mid) : modify(tr[x].r, t, k, mid + 1, r);
    }
    int query (int L, int R, int l = 0, int r = inf, int x = rt)
    {
        if (!x || l > R || L > r)
            return 0;
        if (l >= L && r <= R)
            return tr[x].v;
        int mid = l + r >> 1;
        return max(query(L, R, l, mid, tr[x].l), query(L, R, mid + 1, r, tr[x].r));
    }
}
void solve ()
{
    BIT::init(), PresidentTree::init();
    for (int i = 1; i <= n; i++)
    {
        int t = PresidentTree::query(w[i], inf);
        while (t)
        {
            BIT::modify(t, w[t] - w[i]);
            t = PresidentTree::query(w[i], w[i] + w[t] - 1 >> 1);
        }
        PresidentTree::modify(PresidentTree::rt, w[i], i);
        for (Query j : q[i])
            chkmin(ans[j.id], BIT::query(j.l));
    }
}
int main ()
{
    read(n);
    for (int i = 1; i <= n; i++)
        read(w[i]);
    read(m);
    for (int i = 1, l, r; i <= m; i++)
    {
        read(l), read(r);
        ans[i] = inf;
        q[r].push_back((Query){l, i});
    }
    solve();
    for (int i = 1; i <= n; i++)
        w[i] = inf - w[i];
    solve();
    for (int i = 1; i <= m; i++)
        write(ans[i]), puts("");
    return 0;
}