区間 LIS クエリを書きました

去年末にやるとはいっていませんが、すぐ終わりました。

rsk0315.hatenablog.com

クエリで与えられた区間の最長増加部分列の長さを答えるやつで、計算量は です。

前計算で、全ての区間に対して最長増加部分列の長さを求めておきます。

vector dp(n, vector< int >(n));
for(int i = 0; i < n; i++) {
  vector< int > lis;
  for(int j = i; j < n; j++) {
    auto it = upper_bound(begin(lis), end(lis), a[j]);
    if(it == lis.end()) lis.emplace_back(a[j]);
    else *it = a[j];
    dp[i][j] = (int) lis.size();
  }
}

クエリに答える際は、前計算のテーブルを参照すればよいです。