#466028 (C++14) No.1031 いたずら好きなお姉ちゃん

提出ソース
結果

問題	No.1031 いたずら好きなお姉ちゃん
コンテスト
ユーザー	NyaanNyaan
提出日時	2020-04-17 22:37:13
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	81 ms / 3,500 ms
コード長	10,581 bytes
コンパイル時間	2,404 ms
コンパイル使用メモリ	185,276 KB
実行使用メモリ	11,064 KB
最終ジャッジ日時	2024-10-03 14:16:21
合計ジャッジ時間	6,559 ms
ジャッジサーバーID （参考情報）	judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 53
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma region kyopro_template
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define each(x, v) for (auto &x : v)
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define mem(a, val) memset(a, val, sizeof(a))
#define ini(...)   \
  int __VA_ARGS__; \
  in(__VA_ARGS__)
#define inl(...)         \
  long long __VA_ARGS__; \
  in(__VA_ARGS__)
#define ins(...)      \
  string __VA_ARGS__; \
  in(__VA_ARGS__)
#define inc(...)    \
  char __VA_ARGS__; \
  in(__VA_ARGS__)
#define in2(s, t)                           \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i]);                         \
  }
#define in3(s, t, u)                        \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i]);                   \
  }
#define in4(s, t, u, v)                     \
  for (int i = 0; i < (int)s.size(); i++) { \
    in(s[i], t[i], u[i], v[i]);             \
  }
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
using namespace std;
void solve();
using ll = long long;
template <class T = ll>
using V = vector<T>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vd = V<double>;
using vs = V<string>;
using vvl = vector<vector<long long>>;
using P = pair<long long, long long>;
using vp = vector<P>;
using pii = pair<int, int>;
using vpi = vector<pair<int, int>>;
constexpr int inf = 1001001001;
constexpr long long infLL = (1LL << 61) - 1;
template <typename T, typename U>
inline bool amin(T &x, U y) {
  return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
  return (x < y) ? (x = y, true) : false;
}
template <typename T, typename U>
ll ceil(T a, U b) {
  return (a + b - 1) / b;
}
constexpr ll TEN(int n) {
  ll ret = 1, x = 10;
  while (n) {
    if (n & 1) ret *= x;
    x *= x;
    n >>= 1;
  }
  return ret;
}

template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.first << " " << p.second;
  return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.first >> p.second;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  int s = (int)v.size();
  for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
  return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &... u) {
  cin >> t;
  in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U>
void out(const T &t, const U &... u) {
  cout << t;
  if (sizeof...(u)) cout << " ";
  out(u...);
}
template <typename T>
void die(T x) {
  out(x);
  exit(0);
}

#ifdef NyaanDebug
#include "NyaanDebug.h"
#define trc(...)                   \
  do {                             \
    cerr << #__VA_ARGS__ << " = "; \
    dbg_out(__VA_ARGS__);          \
  } while (0)
#define trca(v, N)       \
  do {                   \
    cerr << #v << " = "; \
    array_out(v, N);     \
  } while (0)
#define trcc(v)                             \
  do {                                      \
    cerr << #v << " = {";                   \
    each(x, v) { cerr << " " << x << ","; } \
    cerr << "}" << endl;                    \
  } while (0)
#else
#define trc(...)
#define trca(...)
#define trcc(...)
int main() { solve(); }
#endif

struct IoSetupNya {
  IoSetupNya() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(7);
  }
} iosetupnya;

#pragma endregion

constexpr long long MOD = /** 1000000007;  //*/ 998244353;

// popcount
inline int popcount(unsigned long long a) { return __builtin_popcountll(a); }
// least significant bit
inline int lsb(unsigned long long a) { return __builtin_ctzll(a); }
// most significant bit
inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); }
// get i-th bit
template <typename T>
inline int getbit(T a, int i) {
  return (a >> i) & 1;
}
// set i-th bit
template <typename T>
inline void setbit(T &a, int i) {
  a |= (1LL << i);
}
// delete i-th bit
template <typename T>
inline void delbit(T &a, int i) {
  a &= ~(1LL << i);
}

// lower_bound
template <typename T>
int lb(const vector<T> &v, const T &a) {
  return lower_bound(begin(v), end(v), a) - begin(v);
}
// upper_bound
template <typename T>
int ub(const vector<T> &v, const T &a) {
  return upper_bound(begin(v), end(v), a) - begin(v);
}

// cumulative sum
template <typename T>
vector<T> mkrui(const vector<T> &v) {
  vector<T> ret(v.size() + 1);
  for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
  return ret;
};

// order
template <typename T>
vector<int> mkord(const vector<T> &v, function<bool(T, T)> f) {
  vector<int> ord(v.size());
  iota(begin(ord), end(ord), 0);
  sort(begin(ord), end(ord), f);
  return ord;
}

// unique
template <typename T>
vector<T> mkuni(const vector<T> &v) {
  vector<T> ret(v);
  sort(ret.begin(), ret.end());
  ret.erase(unique(ret.begin(), ret.end()), ret.end());
  return ret;
}

// BIT

template <typename T>
struct BIT {
  int N;
  int max_2beki;

  vector<T> data;
  // 初期化 1-indexedでデータを管理する 0で初期化
  BIT(int size) {
    N = ++size;
    data.assign(N, 0);
    max_2beki = 1;
    while (max_2beki * 2 <= N) max_2beki *= 2;
  }

  // [0,k](閉区間)の総和 閉区間に注意！
  T sum(int k) {
    if (k < 0) return 0;  // k<0のとき0を返す
    T ret = 0;
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  // [l,r](閉区間)の総和
  inline T sum(int l, int r) { return sum(r) - sum(l - 1); }

  // 一点取得 更新はできないことに注意
  inline T operator[](int k) { return sum(k) - sum(k - 1); }

  // data[k] += x;
  void add(int k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // imos法 [l,r]にxを加算
  void imos(int l, int r, T x) {
    add(l, x);
    add(r + 1, -x);
  }

  // lower_bound sum(i)がval以上となる最小のi
  int lower_bound(T w) {
    if (w <= 0) return 0;
    int x = 0;
    for (int k = max_2beki; k > 0; k /= 2) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // upper_bound sum(i)がvalより大きくなる最小のi
  int upper_bound(T w) {
    if (w < 0) return 0;
    int x = 0;
    for (int k = max_2beki; k > 0; k /= 2) {
      if (x + k <= N - 1 && data[x + k] <= w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

template <typename T, typename F>
struct SegmentTree {
  int size;
  vector<T> seg;
  const F func;
  const T UNIT;

  SegmentTree(int N, F func, T UNIT) : func(func), UNIT(UNIT) {
    size = 1;
    while (size < N) size <<= 1;
    seg.assign(2 * size, UNIT);
  }

  SegmentTree(const vector<T> &v, F func, T UNIT) : func(func), UNIT(UNIT) {
    int N = (int)v.size();
    size = 1;
    while (size < N) size <<= 1;
    seg.assign(2 * size, UNIT);
    for (int i = 0; i < N; i++) {
      seg[i + size] = v[i];
    }
    build();
  }

  void set(int k, T x) { seg[k + size] = x; }

  void build() {
    for (int k = size - 1; k > 0; k--) {
      seg[k] = func(seg[2 * k], seg[2 * k + 1]);
    }
  }

  void update(int k, T x) {
    k += size;
    seg[k] = x;
    while (k >>= 1) {
      seg[k] = func(seg[2 * k], seg[2 * k + 1]);
    }
  }

  void add(int k, T x) {
    k += size;
    seg[k] += x;
    while (k >>= 1) {
      seg[k] = func(seg[2 * k], seg[2 * k + 1]);
    }
  }

  // query to [a, b)
  T query(int a, int b) {
    T L = UNIT, R = UNIT;
    for (a += size, b += size; a < b; a >>= 1, b >>= 1) {
      if (a & 1) L = func(L, seg[a++]);
      if (b & 1) R = func(seg[--b], R);
    }
    return func(L, R);
  }

  T &operator[](const int &k) { return seg[k + size]; }
};

struct UnionFind {
  vector<int> data;
  vi ma, rsz;
  UnionFind(int N) : data(N, -1), rsz(N, 1) {
    ma.resize(N);
    iota(all(ma), 0);
  }

  int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

  int unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    ma[x] = max(ma[x], ma[y]);
    rsz[x] += rsz[y];
    return true;
  }

  int size(int k) { return -data[find(k)]; }

  int same(int x, int y) { return find(x) == find(y); }
};

void solve() {
  ini(N);
  vi a(N);
  in(a);

  // auto f = [](ll a, ll b) { return a + b; };
  ll ans = 0;
  {
    BIT<ll> bit(N + 10);
    set<int> s, t;
    vl val(N + 1);
    UnionFind uf(N + 1);
    rep(i, N) {
#ifdef NyaanDebug
      vi b;
      rep1(i, N) b.push_back(bit.sum(i));
      trc(b);
#endif
      ll c = bit.sum(a[i]);

      trc(i, c);
      trcc(s);
      trcc(t);
      trc();

      ans += c;
      val[a[i]] = c + 1;
      while (!s.empty() && *s.begin() < a[i]) {
        auto it = s.begin();
        bit.imos((*it) + 1, a[i], -uf.rsz[uf.find(*it)]);
        uf.unite(*it, a[i]);
        s.erase(it);
      }
      while (!t.empty() && *t.rbegin() > a[i]) {
        auto it = --t.end();
        int p = uf.find(*it);
        int par = uf.ma[p];
        bit.imos(par + 1, N + 1, -1);
        uf.rsz[p]--;
        t.erase(it);
      }
      // 追加
      s.insert(a[i]);
      t.insert(a[i]);
      bit.imos(a[i] + 1, N + 1, 1);
    }
  }
  reverse(all(a));

  {
    BIT<ll> bit(N + 10);
    set<int> s, t;
    vl val(N + 1);
    UnionFind uf(N + 1);
    rep(i, N) {
#ifdef NyaanDebug
      vi b;
      rep1(i, N) b.push_back(bit.sum(i));
      trc(b);
#endif
      ll c = bit.sum(a[i]);

      trc(i, c);
      trcc(s);
      trcc(t);
      trc();

      ans += c;
      val[a[i]] = c + 1;
      while (!s.empty() && *s.begin() < a[i]) {
        auto it = s.begin();
        bit.imos((*it) + 1, a[i], -uf.rsz[uf.find(*it)]);
        uf.unite(*it, a[i]);
        s.erase(it);
      }
      while (!t.empty() && *t.rbegin() > a[i]) {
        auto it = --t.end();
        int p = uf.find(*it);
        int par = uf.ma[p];
        bit.imos(par + 1, N + 1, -1);
        uf.rsz[p]--;
        t.erase(it);
      }
      // 追加
      s.insert(a[i]);
      t.insert(a[i]);
      bit.imos(a[i] + 1, N + 1, 1);
    }
  }

  out(ans);
}
yukicoder

結果

ソースコード
