Educational Codeforces Round 73 F. Choose a Square (R2500)

「区間」と「二次元平面上の点」とはしばしば互いに行き来することで問題が解けたりする！！！

問題へのリンク

問題概要

二次元平面上の 点が与えられる (いずれも 座標が 0 以上の格子点)。各点にはスコア が与えられる。

対角線のうちの一つが 上にあるような正方形のうち、正方形の内部または辺上の点のスコアの総和から、正方形の一辺の長さを引いた値が最大となるものを求めよ。

制約

• 

考えたこと

一見絶望的な気持ちになったのだが

• 二次元平面上の頂点
• 区間

とが一対一対応していて、一方を他方に置き換えることで問題の見通しがよくなることがよくある。今までは区間を平面上の点とみることで見通しよくなるパターンを多く経験してきたけど、今回は平面上の点を区間としてみると見通しがよくなる。

各点 は区間 [ ] とみなすことができる ( だったら区間 [ ])。そして正方形もまた区間 [ ) と考えることができる。

そうすると、問題は

• 個の区間が与えられる
• 区間であってそこに含まれる区間のスコアん総和から、区間の長さを引いた値が最大となるものを求めよ

という問題と考えることができる。

平面走査へ

区間に関する問題だと思えたならば、区間を始点または終端でソートするのが定石。ここでは始点でソートしてみる。そして

• 各区間の始点を左側とした区間であって
• 各区間の終端を右側とした区間

をすべて考えてスコアが最大のものを求めればよいことになる (与えられた区間の始点終点は始点・終点とよび、問題で考える区間の始点終点は左側・右側とよぶことにする)。ここで、

• まず最も左にある区間の始点を左側として固定したとき
• 右側を各区間の終端に設定した場合のスコアを一旦求めておく

ことにする。そして左側を少しずつ右へ持って行ったときに、各右側のスコアは自然に更新していくことができる。具体的には左側を右に動かしたことによって、区間 [s, t) の s が外れるとき、t よりも右側にある点についてはその区間のスコアを引くことになる。よって

• 区間加算 (全体として 回実施することになる)
• 区間最大値

を求めることのできるセグメントツリーが欲しい。遅延評価つきの Starry Sky Tree がピッタリである。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 区間加算と、区間最大値取得
template<class Monoid, class Action> struct StarrySky {
    const Monoid INF;
    const Action ZERO;
    int SIZE;
    vector<pair<Monoid, int> > dat;
    vector<Action> lazy;
    
    StarrySky(int n, const Monoid &inf, const Action &zero) : INF(inf), ZERO(zero) {
        init(n);
    }
    void init(int n) {
        SIZE = 1;
        while (SIZE < n) SIZE <<= 1;
        dat.assign(SIZE * 2, {-INF, -1});
        lazy.assign(SIZE * 2, ZERO);
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE] = {v, a}; }
    void build() {
        for (int k = SIZE - 1; k > 0; --k)
            dat[k] = max(dat[k*2], dat[k*2+1]);
    }
    
    /* update [a, b) */
    inline void evaluate(int k) {
        if (lazy[k] == ZERO) return;
        if (k < SIZE) lazy[k*2] += lazy[k], lazy[k*2+1] += lazy[k];
        dat[k].first += lazy[k];
        lazy[k] = ZERO;
    }
    inline void update(int a, int b, const Action &v, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b) lazy[k] += v, evaluate(k);
        else if (a < r && l < b) {
            update(a, b, v, k*2, l, (l+r)>>1), update(a, b, v, k*2+1, (l+r)>>1, r);
            dat[k] = max(dat[k*2], dat[k*2+1]);
        }
    }
    inline void update(int a, int b, const Action &v) { update(a, b, v, 1, 0, SIZE); }
    
    /* get [a, b) */
    inline pair<Monoid,int> get(int a, int b, int k, int l, int r) {
        evaluate(k);
        if (a <= l && r <= b)
            return dat[k];
        else if (a < r && l < b)
            return max(get(a, b, k*2, l, (l+r)>>1), get(a, b, k*2+1, (l+r)>>1, r));
        else
            return {-INF, -1};
    }
    inline pair<Monoid,int> get(int a, int b) { return get(a, b, 1, 0, SIZE); }
    inline Monoid operator [] (int a) { return get(a, a+1).first; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE; ++i) { cout << (*this)[i]; if (i != SIZE) cout << ","; }
        cout << endl;
    }
};


const long long INF = 1LL<<60;
using pll = pair<long long, long long>;
using Item = pair<pll, long long>;

int main() {
    int N; cin >> N;
    vector<Item> v(N);
    for (int i = 0; i < N; ++i) {
        cin >> v[i].first.first >> v[i].first.second >> v[i].second;
        if (v[i].first.first > v[i].first.second)
            swap(v[i].first.first, v[i].first.second);
    }
    sort(v.begin(), v.end());

    // 座標圧縮
    vector<long long> alt;
    for (int i = 0; i < N; ++i) {
        alt.push_back(v[i].first.first);
        alt.push_back(v[i].first.second);
    }
    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    alt.push_back(alt.back() + 1);

    // 区間の始点終点で整理
    int M = alt.size();
    vector<vector<int> > ends(M+1), starts(M+1);
    for (int i = 0; i < N; ++i) {
        int right = lower_bound(alt.begin(), alt.end(), v[i].first.second) - alt.begin();
        int left = lower_bound(alt.begin(), alt.end(), v[i].first.first) - alt.begin();
        ends[right].push_back(i);
        starts[left].push_back(i);
    }

    // 初期状態
    StarrySky<long long, long long> ss(M+1, INF, 0);
    long long sum = 0;
    for (int i = 0; i < M; ++i) {
        long long len = alt[i] - alt[0];
        for (auto id : ends[i]) sum += v[id].second;
        ss.set(i, sum - len);
    }
    ss.build();
    auto cur = ss.get(0, M);
    long long res = cur.first;
    int rx = alt[0];
    int ry = alt[cur.second];

    // 区間の左側を一通り試す
    for (int i = 1; i < M; ++i) {
        long long lenadd = alt[i] - alt[i-1];
        ss.update(i, M, lenadd);
        for (auto id : starts[i-1]) {
            int right = lower_bound(alt.begin(), alt.end(), v[id].first.second) - alt.begin();
            ss.update(right, M, -v[id].second);
        }
        auto cur = ss.get(i, M);
        if (res < cur.first) res = cur.first, rx = alt[i], ry = alt[cur.second];
    }
        
    cout << res << endl;
    cout << rx << " " << rx << " " << ry << " " << ry << endl;
}