题解：CF2152F Triple Attack

· · 题解

我知道有人会说我非人哉但我还是要写这篇题解。

由于题目保证 x 单调不降，因此题意转化为选定区间内最大子集使得子集内所有下标差为 2 的元素的差大于 z。

不难证明从第一个或最后一个数开始选，贪心地选中第一个/最后一个（与上面对应）能保持条件满足的元素是最优的。这里我们从第一个数开始选。

首先对于每个数 x_i 预处理其后第一个与其差大于 z 的元素位置，记为 t_i。

接下来，我们定义一个状态为一个二元组 (a,b)。每个二元组 (a,b) 有一个唯一的后继状态，若 t_a=b，则为 (b,t_a+1)；否则为 (b,t_a)。实际上，一个“状态”代表的是一个合法子集的最后两个元素的位置。

由上述定义可知，将区间长度小于 3 的特殊情况判掉之后，查询 (l,r) 的答案即为最大的整数 y+2 使得状态 (l,l+1) 的 y 次后继状态中的两个元素均不大于 r。

每次查询暴力进行上述操作显然无法通过此题，因此考虑使用 map 存储所有的 pair 进行记忆化搜索。然而提交之后会出现 TLE 的情况，因此考虑将 pair 编码为 long long，使用 unordered_map 存储所有编码并进行记忆化搜索，可以在 2.9s 内通过此题。

时间复杂度未知。

这道题在我拥有前五道题的 AC 的基础上进一步扩大了我的优势，使我不仅在本次比赛中取得了 Master 更与 International Master 的距离更近了 60 左右。

// #define Redshift_Debug
#ifdef Redshift_Debug
#define debug(...) fprintf(stderr, __VA_ARGS__)
#include <chrono>
#else
#define debug(...)
#endif
#include <array>
#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;
const int N = 2.5e5 + 10, B = 20;
int n, z, q, a[N], nxt[N];
using pii = pair<int, int>;
using sta = array<pii, B>;
using ll = long long;
ll rmp(pii x)
{
    return 1ll * (x.first - 1) * n + x.second;
}
unordered_map<ll, sta> mp;
void init_global()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
}

void init_local()
{
    mp.clear();
    cin >> n >> z;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
}
void dfs(int x, int y)
{
    if (mp.count(rmp(pii{x, y})))
        return;
    if (nxt[x] + (y == nxt[x]) > n)
    {
        for (auto &i : mp[rmp(pii{x, y})])
            i = {n + 1, n + 1};
        return;
    }
    int tnxt = nxt[x] + (y == nxt[x]);
    dfs(y, tnxt);
    mp[rmp(pii{x, y})][0] = pii{y, tnxt};
    for (int i = 1; i < B; i++)
    {
        mp[rmp(pii{x, y})][i] = mp[rmp(mp[rmp(pii{x, y})][i - 1])][i - 1];
    }
}
void run()
{
    for (int i = 1, j = 1; i <= n; i++)
    {
        while (j <= n and a[j] - a[i] <= z)
            j++;
        nxt[i] = j;
    }
    for (auto &i : mp[rmp(pii{n + 1, n + 1})])
        i = pii{n + 1, n + 1};
    cin >> q;
    for (int i = 1, l, r, res; i <= q; i++)
    {
        cin >> l >> r;
        if (r - l + 1 <= 2)
        {
            cout << r - l + 1 << '\n';
            continue;
        }
        dfs(l, l + 1);
        res = 2;
        pii buf = {l, l + 1};
        for (int i = B - 1; ~i; i--)
        {
            if (mp[rmp(buf)][i].second > r)
                continue;
            res += (1 << i);
            buf = mp[rmp(buf)][i];
        }
        cout << res << '\n';
    }
}
int main()
{
#ifdef Redshift_Debug
    auto st = chrono::high_resolution_clock::now();
#endif
    int T = 1;
    init_global();
    cin >> T;
    while (T--)
    {
        init_local();
        run();
    }
#ifdef Redshift_Debug
    auto ed = chrono::high_resolution_clock::now();
    fprintf(stderr, "%.9lf\n", (ed - st).count() / 1e9);
#endif
}