codeforces #361 div2 D. Friends and Subsequences

問題ページ
Problem - D - Codeforces

sparseTableのverifyとして解いた。

解法

• 区間の左端lを固定して考えてみる
• 区間[l,r]についてmax(a) - min(b)を考えると単調に増えていく
• max(a) - min(b) の数列は [-2, -1, -1, 0, 0, 0, 0, 1, 2, 3] みたいな単調増加する列になるはず
• この数列で0の数を数えれば左端がlのとき条件を満たす区間の数がわかる
• 0の数を数えるのは二分探索をつかえばできる
• 区間max,minを取るのはsparsetableでO(1)なので二分探索の判定はO(1)でできる
• したがって合計O(nlogn)でできる

ソースコード

#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

constexpr auto LLINF = (1LL<<60);
constexpr auto INF = (1LL<<30);
constexpr auto MOD = 1e9+7;

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};

template <typename S>
class sparseTable {
public:
  using T = typename S::T;
  int n;
  vector<int> log2;
  vector<vector<T>> t;

  sparseTable(int nn) {
    n = nn;
    log2.assign(n+1, 0);
    for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
    t = vector<vector<T>>(log2[n]+1, vector<T>(n));
  }
  void init(vector<T> v) {
    for(int i=0; i<n; ++i) t[0][i] = v[i];
    for(int j=1; j<=log2[n]; ++j) {
      int w = 1LL<<(j-1);
      for (int i = 0; i+(w<<1) <= n; ++i) {
        t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
      }
    }
  }
  // [l, r]
  T query(int l, int r) {
    int j = log2[r - l];
    return S::op(t[j][l], t[j][r-(1 << j)+1]);
  }
};

// 集合T、結合則・可換・冪等律が成り立つ二項演算op
struct minnimum {
  using T = int;
  static T op(const T& a, const T& b) { return min(a, b); }
};
struct maximum {
  using T = int;
  static T op(const T& a, const T& b) { return max(a, b); }
};

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

  sparseTable<maximum> sp1(n);  sp1.init(a);
  sparseTable<minnimum> sp2(n); sp2.init(b);

  int ret = 0;
  REP(l, n) {
    if(a[l] > b[l]) continue;

    // (lb, ub]
    int lb = l-1, ub = n-1;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(sp1.query(l, mid) - sp2.query(l, mid) >= 0) {
        ub = mid;
      } else {
        lb = mid;
      }
    }
    int rmin = ub;
    if(sp1.query(l, rmin) != sp2.query(l, rmin)) continue;

    // [lb, ub)
    lb = l, ub = n;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      if(sp1.query(l, mid) - sp2.query(l, mid) <= 0) {
        lb = mid;
      } else {
        ub = mid;
      }
    }
    int rmax = lb;

    ret += rmax - rmin + 1;
  }

  cout << ret << endl;
  return 0;
}