Codeforces Round 990 赛后复盘

E. Adventurers

游记

赛时看到这道题，第一反应是：“我糙，二维偏序，我不会啊”，确实二维偏序能实现，但不是最优的。

哎哎，现在来看好简单，蠢死我得了。

题解

可知对于我们选择的点 $[x_{0}, y_{0}]$ ，当且仅当所选的两个点划分出的边界 “内部” 有点时，答案才会发生变化，所以答案的横纵坐标范围一定不会超出点集的横纵坐标范围。

所以就有，我们可以对点集坐标做离散化处理（这里可以简单地直接对横纵坐标分别离散化，原因可以自己想想）。

处理之后，就有：我们可以枚举答案的横坐标，这一步骤的开销是 $Θ (n)$ 的，然后在这基础上二分答案，我们怎么检查在这个横坐标处对答案 $k$ 是否存在合法的解呢？

很容易想到，我们在当前的左半边找到第 $k$ 大与第 $k$ 小的数，再在右半边也这样子找，如果找到的这些数所代表的那 $k$ 个点可以被一条直线分成上下两段（也就是最大集下界严格高于最小集上界），那么一定存在答案，且答案明显就是当前点横坐标 + 1 与上下界之间的任意一点（注意依题意不能与下界重合）。

那现在最大的问题来了：怎么求取动态集合中的第 $k$ 小值？

当然，方法很多：平衡二叉搜索树 / 权值线段树 / 甚至主席树都可以完美解决

但是我们想要让代码量尽量减小，同时常数也尽可能地小，再加上我们已经做了离散化处理，所以只需要权值树状数组就可以了

最后再做一点优化：

如果区间内不满 $2 k$ 个点，那一定不可能有答案，Pass。
如果目前已知能取到答案 $k$ ，那么显然，再去检查比 $k$ 小的答案情况是没有意义的，每次只需从当前最优答案 + 1 开始检查

AC 代码

c++

#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;

mt19937_64 rnd(time(0));

typedef long long ll;
typedef uint64_t ull;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt;

template <typename T> struct Fenwick {
    ll n{};
    vector<T> a;
    Fenwick(ll _n = 0) { init(_n); }
    void init(ll _n) { a.assign(n = _n, T{}); }
    void add(ll x, const T &k) {
        for (ll i = x + 1; i <= n; i += i & -i)
            a[i - 1] = a[i - 1] + k;
    }
    T sum(ll x) {
        T ans{};
        for (ll i = x; i > 0; i ^= i & -i)
            ans = ans + a[i - 1];
        return ans;
    }
    T rangeSum(ll l, ll r) { return sum(r) - sum(l - 1); }
    ll select(const T &k) {
        ll x{};
        T cur{};
        for (ll i = 1 << __lg(n); i; i >>= 1)
            if (x + i <= n && cur + a[x + i - 1] <= k) {
                x += i;
                cur = cur + a[x - 1];
            }
        return x;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt;

    while (tt--) {
        ll n;
        cin >> n;
        vector<ll> x(n), y(n);
        for (ll i = 0; i < n; i++)
            cin >> x[i] >> y[i];
        auto xs = x, ys = y;
        sort(xs.begin(), xs.end());
        sort(ys.begin(), ys.end());

        xs.erase(unique(xs.begin(), xs.end()), xs.end());
        ys.erase(unique(ys.begin(), ys.end()), ys.end());

        for (ll i = 0; i < n; i++) {
            x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin();
            y[i] = lower_bound(ys.begin(), ys.end(), y[i]) - ys.begin();
        }

        Fenwick<ll> fl(n), fr(n);

        vector<ll> p(n);
        iota(p.begin(), p.end(), 0);
        sort(p.begin(), p.end(),
             [&](int i, int j) { return x[i] < x[j]; });

        for (ll i = 0; i < n; i++)
            fr.add(y[i], 1);

        //		for(ll i=0;i<n;i++)
        //			cout<<fr.select(i)<<' ';
        //		cout<<endl;

        ll k = 0, ansx{}, ansy{};
        for (ll i = 0; i < n; i++) {
            ll j = p[i];
            fl.add(y[j], 1);
            fr.add(y[j], -1);
            if (i + 1 < n && x[j] == x[p[i + 1]])
                continue;
            while (1) {
                if (i + 1 < 2 * (k + 1) || n - i - 1 < 2 * (k + 1))
                    break;
                ll top = max(fl.select(k), fr.select(k));
                ll flr = min(fl.select((i + 1) - (k + 1)),
                             fr.select(n - (i + 1) - (k + 1)));
                if (top >= flr)
                    break;

                //				cout<<k<<' '<<top<<'
                //'<<flr<<endl;

                k++;
                ansx = xs[x[p[i]]] + 1;
                ansy = ys[flr];
            }
        }
        //		OOO
        cout << k << endl << ansx << ' ' << ansy << endl;
    }

    cout.flush();

    return 0;
}

Codeforces Round 990 赛后复盘 ​

E. Adventurers ​

游记 ​

题解 ​

AC 代码 ​

Codeforces Round 990 赛后复盘

E. Adventurers

游记

题解

AC 代码