mayoko’s diary

プロコンとかいろいろ。

CodeChef Chef and his study plans

問題

Contest Page | CodeChef

N 個の区間 [Si, Ei] が与えられる。以下の Q 個のクエリに答えよ。

  • s, e が与えられるので, 上記 N 個の区間のうち, [s, e] におさまるものの個数の最大値を求める。ただし, 区間同士は交差してはいけない。i.e. [Si, Ei] と [Sj, Ej] があったとして, Ei < Sj または Ej < Si
解法

クエリでないなら, よくある有名な貪欲法で解けます(Ei についてソートしていくやつ)。
ただ, 今回の場合はクエリに答えていかないといけないので, 1 個あたり O(log N) くらいで答えなければなりません。上記の方法は 1 つあたり O(N) かかるのでダメです。

で, それにはダブリングを使えば良いような気がします。ただ, 問題点があって, [s, e] が与えられたとき, 最初の区間をどう選べば良いかわかりません。

しかし, 以下のようにしてあらかじめ余計な区間を取り除いておくと, N 個の区間として, ソートすると Si < Sj かつ Ei < Ej (i < j) をみたすようなものだけを残すことができるので, 明らかに 「s <= Si を満たす最初の i」を最初に選ぶ区間にすれば良いことが分かります。

余計な区間の取り除く方針ですが,

  • E の値が同じとき, S の値が小さいものは余計(S が小さいものを使えば直前の E が大きくてもなんとかなるかもしれない)
  • Ei < Ej の時, Si > Sj だったら [Sj, Ej] は余計(i のほうが区間が小さいので断然有利)

ということを考えれば良いです(これを考えると Si < Sj かつ Ei < Ej (i < j) になる)。

ダブリングは蟻本に書いてあるのですぐ思いついたんですが区間取り除くのを全く考えなかったので解けなかった…基本テクっぽいので覚えておきます。

const int MAXN = 100100;
const int MAXLOGN = 20;
int parent[MAXLOGN][MAXN];

int query(int s, int e, const vector<pii>& P) {
    int i = lower_bound(P.begin(), P.end(), pii(s, 0)) - P.begin();
    if (i >= P.size() || P[i].second > e) return 0;
    int ans = 1;
    for (int j = MAXLOGN-1; j >= 0; j--) {
        int nxt = parent[j][i];
        if (nxt == -1 || P[nxt].second > e) continue;
        ans += 1<<j;
        i = nxt;
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N >> Q;
    vector<pii> P;
    {
        vector<pii> tmp(N);
        for (int i = 0; i < N; i++) {
            cin >> tmp[i].second >> tmp[i].first;
            tmp[i].second *= -1;
        }
        sort(tmp.begin(), tmp.end());
        P.push_back(tmp[0]);
        for (int i = 1; i < N; i++) {
            auto pre = P.back(); pre.second *= -1;
            auto nxt = tmp[i]; nxt.second *= -1;
            if (pre.first < nxt.first && pre.second < nxt.second) P.push_back(tmp[i]);
        }
        for (auto& p : P) {
            p.second *= -1;
            swap(p.first, p.second);
        }
    }
    memset(parent, -1, sizeof(parent));
    N = P.size();
    for (int i = 0; i < N; i++) {
        parent[0][i] = lower_bound(P.begin(), P.end(), pii(P[i].second+1, 0)) - P.begin();
        if (parent[0][i] == N) parent[0][i] = -1;
    }
    for (int i = 0; i < MAXLOGN-1; i++) {
        for (int v = 0; v < N; v++) {
            if (parent[i][v] == -1) parent[i+1][v] = -1;
            else parent[i+1][v] = parent[i][parent[i][v]];
        }
    }
    while (Q--) {
        int s, e;
        cin >> s >> e;
        cout << query(s, e, P) << endl;
    }
    return 0;
}