AtCoder Regular Contest 126B

ARC126
一般化したLIS.

LIS
　まず普通のLISを考える． vector に対して，連続するとは限らない部分列であって 狭義単調増加になるもののうち，最長の長さを求める問題． 増加列は2つの図形的な捉え方がある．
　一つ目は，の組を頂点として2次元平面に図示すれば， 右肩上がりに頂点を選ぶことになる．
　二つ目は，との頂点をそれぞれ列に並べて平行に置き， 部分列として使うを辺で結んだとき， 辺同士が交わらないことと言える．

一般化したLIS
　今回の問題は，LISの二つ目の方法と同じ． つまり，LISの一つ目の方法とみなせる．

　の組を2次元平面に図示する． LISとの違いは，LISにおいては一つのに対してはただ一つであった．

　今回の問題は， 一つのの値に対して対応するが複数有り得る． 同じに対しては，出来るだけ小さいを採用したい． そこで，各に対して対応するの元を集めたベクトルを作り， 降順ソートをして実現できる．

使っている記号

template<typename T> int lwb(const vector<T>& a, const T& x) { return lower_bound(all(a), x) - a.begin();}

int main() {

  ll n, m, k, q;

  cin >> n >> m;

  vector<pll> v;

  rep(i,m){

    ll a,b; cin >> a >> b;

    --a, --b;

    v.emplace_back(a,-b);

  }

  sort(all(v));

  vll p;

  rep(i,m){

    p.emplace_back(-v[i].second);

  }

  vll dp(m+1, INFL);

  dp[0] = -1;

 

  ll ans = -1;

  for(ll x: p){

    ll j = lwb(dp, x);

    dp[j] = x;

    chmax(ans, j);

  }

  cout << ans << endl;

  return 0;

}