Codeforces Round #462 (Div. 2) C. A Twisty Movement

問題ページ Problem - C - Codeforces

考えたこと

• 非減少列の判定が連続でなくてもいいことに気付かずに時間を溶かす
• 反転するのは1→2に移るところ～2→1に移るところ以外考えなくてよさそう
• [0,l) [l,r] (r,n-1] に分けると[l,r]に1から2に移るところがあるはず
• [0,l) に1が何個あるか、(r,n-1] に2が何個あるかはそれぞれ累積和を取っておけば求められそう
• [l,r]で条件を満たす最長の部分列の長さを高速で求められればO(n^2f(n))みたいな計算量でいけそう
• 2から1に移るタイミングをO(r-l)で全探索すれば求められるけどTLE
• k番目 (l<=k<=r)で2から1に移るとき[l,k)の2の数と[k,r]の1の数の和が部分列の長さになる
• これのmaxを取れれば[l,r]で最長の部分列が求まりそう
• 区間maxなのでセグ木の気持ちになる
• 色々累積和を取っておいてセグ木を使うと O(n^2logn) なので書くと通る

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

int a[2010];
int dp1f[2010], dp2f[2010], dp1b[2010], dp2b[2010];

template <typename monoid>
class segmentTree {
public:
  using M = monoid;
  using T = typename M::value_type;

  int sz;
  vector<T> x;

  segmentTree(int n = 1e5) {
    sz = 1; while(sz < n) sz *= 2;
    init();
  }
  void init() { x.assign(sz*2, M::id()); }

  // [a, b)
  T query(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return M::id();
    if(a <= l && r <= b) return x[k];
    return M::f(query(a, b, 2*k+1, l, (l+r)/2),
                query(a, b, 2*k+2, (l+r)/2, r));
  }
  T query(int a, int b) {return query(a, b, 0, 0, sz);}
  // 点更新
  void update(int i, const T &val) {
    i += sz-1;
    x[i] = M::g(x[i], val);
    while(i > 0) {
      i = (i-1) / 2;
      x[i] = M::f(x[i*2+1], x[i*2+2]);
    }
  }
};

template <typename T>
struct min_monoid {
  using value_type = T;
  static constexpr T id() { return std::numeric_limits<T>::max(); }
  static T f(const T &a, const T &b) { return min(a, b); }
  static T g(const T &a, const T &b) { return b; }
};
template <typename T>
struct max_monoid {
  using value_type = T;
  static constexpr T id() { return std::numeric_limits<T>::min(); }
  static T f(const T &a, const T &b) { return max(a, b); }
  static T g(const T &a, const T &b) { return b; }
};
template <typename T>
struct sum_monoid {
  using value_type = T;
  static constexpr T id() {return 0;}
  static T f(const T &a, const T &b) { return a+b; }
  static T g(const T &a, const T &b) { return a+b; }
};

template <typename T>
using rmq = segmentTree<max_monoid<T>>;
template <typename T>
using rsq = segmentTree<sum_monoid<T>>;

signed main(void)
{
  int n;
  cin >> n;
  REP(i, n) cin >> a[i];

  REP(i, n) {
    if(a[i] == 1) dp1f[i] = 1, dp1b[i] = 1;
    else dp2f[i] = 1, dp2b[i] = 1;
  }

  FOR(i, 1, n) {
    dp1f[i] += dp1f[i-1];
    dp2f[i] += dp2f[i-1];
  }
  for(int i=n-2; i>=0; --i) {
    dp1b[i] += dp1b[i+1];
    dp2b[i] += dp2b[i+1];
  }

  rmq<int> seg(n);
  REP(i, n) seg.update(i, dp1b[i]+dp2f[i]);

  int ans = 0;
  FOR(i, 0, n) {
    FOR(j, i+1, n+1) {
      int ret = seg.query(i, j) - dp1b[j] - (i==0?0:dp2f[i-1]);
      chmax(ans, dp1f[i-1] + ret + dp2b[j]);
    }
  }
  cout << ans << endl;

  return 0;
}