CS Academy Dominant Free Sets

リンク : https://csacademy.com/contest/archive/task/dominant-free-sets/

問題概要

N個の頂点の座標が与えられる。任意の二頂点をP,Qとすると P_x>=Q_x と P_y>=Q_y を満たすものが存在しない、頂点の集合の選び方は何通りか+7の余りを求めよ。

解説

dp[i] : i番目の頂点を集合に含むときの通り数 とすると、dp[i]=sum{j=0,1...n}{ if(!(i_x>=j_x&&i_y>=j_y)) dp[j]} となるだろう。しかし、これではdp[i]を求めることができない。なので、決める順番を決めることにする。今回はy座標でソートする。dp[i]をソート後のi番目の頂点を集合に含み、i番目までの頂点しか集合に含まないときの通り数とすると、dp[i]=sum{j=0,1...i-1}{if(j_x>i_x)dp[j]}+1(この「+1」はiの頂点のみの場合) と置くことができる。ここでsumの部分は区間の総和であるため、セグ木で高速化することができる。

LL n, ans,dp[110000];
Pll pos[110000];
Seg seg(110000);
int main() {
    cin >> n;
    rep(i, n) {
        cin >> pos[i].fir >> pos[i].sec;
    }
    sort(pos, pos + n, [](Pll x, Pll y) {return x.sec == y.sec ? x.fir < y.fir : x.sec < y.sec; });
    rep(i, n) {
        dp[i] = seg.getsum(pos[i].fir+1, 100001) + 1;
        seg.add(pos[i].fir, dp[i]);
    }
    rep(i, n) {
        ans += dp[i];
        ans %= MOD;
    }
    cout << ans<< endl; 
    return 0;
}