2020-01-12

Codeforces #613 (Div. 2) E. Delete a Segment (R2300)

Codeforces 制約:複数系列の長さの合計が10^5以下クエリ処理問題いもす法各kに対して区間区間ソート累積和座標圧縮差分更新データ構造クエリ:削除イベントソート平面走査 CodeforcesDIV2 CodeforcesR2300 N個の区間の問題 N個のものうち1個を変更・削除したものを解く最大回数・最大個数を求める最適化問題

嘘に悩んだ。なぜ嘘だと気付けなかった...

問題へのリンク

問題概要

以下の問いに $Q$ 回答えよ (各問いは完全独立)。

$N$ 個の区間 $\lbrack l_i, r_i \rbrack$ が与えられる。これらの区間の Union 個数とは、重なりのある部分をマージしてできるグループの個数のことである。

$N$ 個の区間からどれか 1 つの区間を取り除く方法のうち、残りの $N-1$ 個の区間の Union 個数が最大となるものを求め、その最大値を答えよ。

制約

$1 \le Q \le 10^{4}$
$1 \le N \le 2 \times 10^{5}$
各クエリの $N$ の総和が $2 \times 10^{5}$ 以下

考えたこと

クエリと言われると苦手意識あるけど、これは単に $N$ 個の区間に関する問題を $O(N)$ とか $O(N\log{N})$ で解いてください、という話になる。

まずは単純に、「与えられた $N$ 個の区間の Union 数を求める」という問題を考えてみる。これは大きく 2 通りの方法がありそう

座標圧縮して、いもす法する
区間ソートして併合していく、離れた場所が登場したらインクリメント

多分どちらの方針でも、「各区間を取り除いたらどうなるか」を求められそうだけど、1 の方針でやってみる。

いもす法

とりあえず区間の右側を開区間にする。そして最初に座標圧縮しておく。今回の問題、区間 [2, 3) と区間 [3, 7) とは重なりがなくて、2 グループという判定になるけど、ちょっと扱いづらい気がするから全体を 2 倍して、右側を奇数にしておく。

[2, 3) -> [4, 5)
[3, 7) -> (6, 13)

こうしても答えは変わらないはず。まずいもす法すると、"1 以上" と "0" が連続して並んだ箇所の個数が Union 数になる (ただし右端は 0 であるとする)。

そしてここから区間 $\lbrack l, r)$ を取り除くとどうなるかを考える。その区間を一様に 1 減らすことになる。

2 以上のマスについては、減っても Union 数に影響はない
1 が書かれたマスについては、0 になると Union 数を増やす可能性がある
- 正確には、1 が連続している箇所がすべて 0 になっても、寄与するのは「連続する 1 の左端」のみ
0 が書かれたマスを 1 減じることはありえない

というわけで、「左端の 1」がどこにあるのかをメモする配列 v を用意して、その累積和をとると良さそうである。

区間 [l, r) を取り除くとき、左端はややこしいので、区間 [l + 1, r) についての v の総和を求める
左端を補正
右端を補正

することでできそう。計算量は座標圧縮がボトルネックで $O(N\log{N})$ になりそう。

他の方針

他の提出を見てると、イベントソート系の実装が多かった。平面走査的なノリで解いてそう。

嘘解法

こだわってしまった嘘はこちら。DP 的な考え方で、

「まだ飛ばしていない」ときの (個数の最大値, 右端の最小値) のペア
「すでに飛ばした」ときの (個数の最大値, 右端の最小値) のペア

を更新していくというもの。この辞書順で DP すればよいと思ったけどそれは嘘。「個数は小さくても後から回収できる」というパターンがありうる。

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

int N;
vector<long long> l, r;
vector<long long> alt, cl, cr;

long long solve() {
    // 座標圧縮しながら 2 倍する
    alt.clear();
    for (int i = 0; i < N; ++i) alt.push_back(l[i]), alt.push_back(r[i]);
    sort(alt.begin(), alt.end());
    alt.erase(unique(alt.begin(), alt.end()), alt.end());
    cl.resize(N); cr.resize(N);
    for (int i = 0; i < N; ++i) {
        int itl = lower_bound(alt.begin(), alt.end(), l[i]) - alt.begin();
        cl[i] = itl * 2;
        int itr = lower_bound(alt.begin(), alt.end(), r[i]) - alt.begin();
        cr[i] = itr * 2 - 1;
    }

    // imos
    vector<long long> imos(N*5+1, 0);
    for (int i = 0; i < N; ++i) imos[cl[i]]++, imos[cr[i]]--;
    for (int i = 0; i+1 < imos.size(); ++i) imos[i+1] += imos[i];
    int offset = 0;
    for (int i = 0; i+1 < imos.size(); ++i) if (imos[i] && !imos[i+1]) ++offset;
    
    // 1 の位置
    vector<int> ichi(imos.size() + 1, 0), sichi(imos.size() + 1, 0);
    for (int i = 0; i < imos.size(); ++i) {
        // 左端の 1 の場所に 1 を立てる
        if (imos[i] == 1 && (i == 0 || imos[i-1] != 1)) ichi[i] = 1;
        sichi[i+1] = sichi[i] + ichi[i];
    }

    // 各区間
    int res = 0;
    for (int i = 0; i < N; ++i) {
        int left = cl[i], right = cr[i];
        int add = sichi[right] - sichi[left+1];

        // 左端 (減る可能性あり)
        if (left > 0 && ichi[left] == 1 && imos[left-1] > 0) ++add;

        // 右端 (減る可能性あり)
        if (imos[right-1] == 1 && imos[right] == 0) --add;

        res = max(res, offset + add);
    }
    return res;
}

int main() {
    int Q; cin >> Q;
    for (int _ = 0; _ < Q; ++_) {
        cin >> N;
        l.resize(N); r.resize(N);
        for (int i = 0; i < N; ++i) cin >> l[i] >> r[i], ++r[i];
        cout << solve() << endl;
    }
}