专栏文章

题解：CF2138B Antiamuny Wants to Learn Swap

EEngulf
CF2138B题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@minyo3o2
此快照首次捕获于
2025/12/02 10:30
3 个月前
此快照最后确认于
2025/12/02 10:30
3 个月前
查看原文
结论：f([l,r])≠g([l,r])f([l, r]) \neq g([l, r]) 的充要条件是：区间 [l,r][l, r] 存在 l≤i<j<k≤r ∧ ai>aj>akl \le i < j < k \le r \ \wedge \ a_i > a_j > a_k。
充分性：若区间 [l,r][l, r] 存在 l≤i<j<k≤r ∧ ai>aj>akl \le i < j < k \le r \ \wedge \ a_i > a_j > a_k，当交换相邻两项使得 j=i+1,k=j+1j = i + 1, k = j + 1 的时候，因为要最小化 ff，肯定会执行一次操作 2，直接交换 aia_i 和 aka_k，跳过 aja_j，省下 11 次操作，所以 f([l,r])≠g([l,r])f([l, r]) \neq g([l, r])。
必要性：冒泡排序一个区间的操作数是恒定的，但 f([l,r])≠g([l,r])f([l, r]) \neq g([l, r])，说明 一定执行了操作 2。而操作 2 只有在 [aj−1,aj,aj+1] ∧ aj−1>aj>aj+1[a_{j - 1}, a_j, a_{j + 1}] \ \wedge \ a_{j - 1} > a_j > a_{j + 1} 的时候操作，才能比操作 1 省下 11 次，使得 f([l,r])≠g([l,r])f([l, r]) \neq g([l, r])，而又因为最多执行 11 次操作 2，所以 aj−1a_{j - 1} 和 aj+1a_{j + 1} 可以分别往前往后移动。于是区间 [l,r][l, r] 就会存在 l≤i<j<k≤r ∧ ai>aj>akl \le i < j < k \le r \ \wedge \ a_i > a_j > a_k。
充要条件可以归约问题。
问题转化为，qq 次询问区间 [l,r][l, r] 是否存在 l≤i<j<k≤r ∧ ai>aj>akl \le i < j < k \le r \ \wedge \ a_i > a_j > a_k。
我们肯定希望 i,ki, k 离 jj 越近越好，这样可以覆盖到更多的询问。所以我们要求出：
  • i<j ∧ ai>aji < j \ \wedge \ a_i > a_j 最大的 ii；
  • k>j ∧ ak<ajk > j \ \wedge \ a_k < a_j 最小的 kk。
这是经典问题，可以单调栈 Θ(n)\Theta(n) 求出。
现在，每个 jj 可以对 l≤i<k≤rl \le i < k \le r 的询问 [l,r][l, r] 贡献，就是对于每个询问，寻找是否存在 l≤i<k≤rl \le i < k \le r，这是二维偏序问题，可以离线 + 树状数组解决。
O((n+q)log⁡(n+q))\mathcal{O}((n + q)\log (n + q))，瓶颈实际上是排序？？
实现CPP
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;

#ifdef ONLINE_JUDGE
#define debug(...) 0
#else
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#endif

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int tt;
    cin >> tt;
    while (tt--) {
        int n, q; cin >> n >> q;
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];

        stack<int> stk;
        vector<int> lef(n, -1), rig(n, -1);
        stk.emplace(0);
        for (int i = 1; i < n; i++) {
            while (stk.size() && a[stk.top()] < a[i]) stk.pop();
            if (stk.size()) lef[i] = stk.top();
            stk.emplace(i);
        }
        while (stk.size()) stk.pop();
        stk.emplace(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            while (stk.size() && a[stk.top()] > a[i]) stk.pop();
            if (stk.size()) rig[i] = stk.top();
            stk.emplace(i);
        }
        vector<int> vec(n);
        using natsu = tuple<int, int, int, int>;
        vector<natsu> que;
        for (int i = 1; i < n - 1; i++) {
            if (lef[i] < 0 || rig[i] < 0) continue;
            lef[i]++, rig[i]++;
            que.emplace_back(lef[i], rig[i], 0, 0);
        }
        vector<int> ans(q);

        for (int i = 0; i < q; i++) {
            int l, r; cin >> l >> r;
            que.emplace_back(l, r, i, 1);
        }

        sort(que.begin(), que.end(), [](natsu x, natsu y) {return get<0>(x) != get<0>(y) ? get<0>(x) > get<0>(y) : get<3>(x) < get<3>(y);});

        vector<int> bit(n + 1);

        for (auto [l, r, id, op]: que) {
            if (op == 0) for (; r <= n; r += r & -r) bit[r]++;
            else for (; r; r -= r & -r) ans[id] |= bit[r];
        }

        for (int i = 0; i < q; i++)
            cout << (ans[i] ? "NO\n" : "YES\n");
    }
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...