CS Academy 048 D. Dominant Free Sets

CS Academy 048 D. Dominant Free Sets

CS Academy

感想

アルゴリズムの正当性を証明していたにも$\ AC\ $できず......。結局FenwickTreeのクエリ処理時にMODをとっていなかっただけだった。

解法

まず$\ x\ $に関してソートしておき、その列の上で順に$\ y\ $を見ていくことを考える。取り出す部分列の中で、ある$\ i\ $について、$\ x_i < x_{i + 1}\ $となっているならば、$\ y_i > y_{i + 1}\ $となっていればよい。$\ x_i = x_{i + 1}\ $となっているならば、$\ y\ $はどうなっていてもいけない（$\ =\ $は$\ \leq\ $でもあり$\ \geq\ $でもあるからだ）。これは結局、$\ x\ $が同じものについては$\ y\ $についてソートしておけばよい（つまり普通にペアのソートをする）。

そうすると、$\ y\ $の数列について、狭義単調減少な部分列の個数を求める問題に帰着する。これをdpで求める。

dp[i] := i - 1までの、y[i]より大きい数を末尾とする部分列の個数 + 1（自分自身だけで作る部分列の個数）+ dp[i - 1]（自分自身を使わない部分列の個数）

となる。最初の2項が自分自身が末尾になる部分列の個数であるから、その値を保存しておきたい。そしてその総和をとりたいので、FenwickTreeで位置y[i]にその値を加えることで、うまく総和をとれるようにする。

あとは正しくMODをとりながら計算してdp[n - 1]を出力する。

実装

#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()
#define mp      make_pair
#define pii     pair<int, int>
#define ll      long long

static const int MOD = 1000000007;

//0-origin
template <typename T>
struct FenwickTree {
	vector<T> data;
	FenwickTree(int n) : data(n, 0) {}
        //v[i] += x
	void add(int i, T x) { for (int p = i; p < (int)data.size(); p |= p + 1) data[p] += x; }
        //[0, i)
	T sum(int i) {
		T s = 0;
                for (int p = i - 1; p >= 0; p = (p & (p + 1)) - 1) s += data[p];
		return s;
	}
        //[l, r)
	T sum(int l, int r) { return sum(r) - sum(l); }
};

void solve() {
        int n;
        cin >> n;
        vector<pair<long long, long long>> p(n);
        for (int i = 0; i < n; i ++) cin >> p[i].first >> p[i].second;
        sort(all(p));
        FenwickTree<long long> ft(101010);
        vector<long long> v(n);
        for (int i = 0; i < n; i ++) v[i] = p[i].second;
        long long dp[101010];
        dp[0] = 1;
        for (int i = 0; i < n; i ++) {
                long long sum = ft.sum(v[i] + 1, 101010) % MOD;
                ft.add(v[i], (sum + 1) % MOD);
                dp[i] = ((i == 0 ? 0 : dp[i - 1]) + sum + 1) % MOD;
        }
        cout << dp[n - 1] % MOD << endl;
        return;
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        solve();
        return 0;
}