結果

問題 No.956 Number of Unbalanced
ユーザー risujirohrisujiroh
提出日時 2019-12-19 01:10:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 392 ms / 2,000 ms
コード長 4,482 bytes
コンパイル時間 2,198 ms
コンパイル使用メモリ 182,840 KB
実行使用メモリ 23,652 KB
最終ジャッジ日時 2024-07-06 23:14:05
合計ジャッジ時間 8,780 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}

template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << ' ' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define DEBUG(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

template<class T, T Op(T, T), T E(), class U, T Ap(T, U), U Cp(U, U), U Id()>
struct SegmentTree {
  const int n;
  vector<T> t;
  vector<U> u;
  SegmentTree(int _n) : n(_n), t(2 * n, E()), u(n, Id()) {}
  T& operator[](int i) { return t[i + n]; }
  void build() {
    for (int i = n - 1; i >= 1; --i) t[i] = Op(t[2 * i], t[2 * i + 1]);
  }
  void push() { for (int i = 1; i < n; ++i) push(i); }
  void apply(int i, U f) {
    t[i] = Ap(t[i], f);
    if (i < n) u[i] = Cp(u[i], f);
  }
  void push(int i) {
    if (u[i] == Id()) return;
    apply(2 * i, u[i]);
    apply(2 * i + 1, u[i]);
    u[i] = Id();
  }
  void push(int l, int r) {
    for (int hl = __lg(l + n), hr = __lg(r - 1 + n); hr > 0; --hl, --hr) {
      int al = (l + n) >> hl, ar = (r - 1 + n) >> hr;
      if (al < n) push(al);
      if (ar != al) push(ar);
    }
  }
  T acc(int l, int r) {
    push(l, r);
    T a = E(), b = E();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) a = Op(a, t[l++]);
      if (r & 1) b = Op(t[--r], b);
    }
    return Op(a, b);
  }
  T get(int i) { return acc(i, i + 1); }
  void act(int l, int r, U f) {
    push(l, r);
    for (int i = l + n, j = r + n; i < j; i >>= 1, j >>= 1) {
      if (i & 1) apply(i++, f);
      if (j & 1) apply(--j, f);
    }
    l = (l + n) >> __builtin_ctz(l + n);
    while (l >>= 1) t[l] = Op(t[2 * l], t[2 * l + 1]);
    r = (r + n) >> __builtin_ctz(r + n);
    while (r >>= 1) t[r] = Op(t[2 * r], t[2 * r + 1]);
  }
  void set(int i, T a) {
    push(i, i + 1);
    t[i += n] = a;
    while (i >>= 1) t[i] = Op(t[2 * i], t[2 * i + 1]);
  }
};

struct T { long long v, c; };
T add(T a, T b) { return {a.v + b.v, a.c + b.c}; }
T zero() { return {0, 0}; }
T add(T a, long long f) { return {a.v + f * a.c, a.c}; }
long long add(long long f, long long g) { return f + g; }
long long zeroll() { return 0; }

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> a(n);
  for (auto&& e : a) {
    cin >> e;
    --e;
  }
  vector< vector<int> > idx(1e5);
  for (int i = 0; i < n; ++i) {
    idx[a[i]].push_back(i);
  }
  SegmentTree<T, add, zero, long long, add, add, zeroll> st(2 * n + 1);
  SegmentTree<T, add, zero, long long, add, add, zeroll> sum(2 * n + 1);
  for (int i = 0; i <= 2 * n; ++i) {
    st[i] = {0, i};
    sum[i] = {0, 1};
  }
  st.build();
  sum.build();
  long long res = 0;
  for (int v = 0; v < 1e5; ++v) {
    if (idx[v].empty()) {
      continue;
    }
    DEBUG(v, idx[v]);
    vector<int> b;
    for (int t = 0; t < (int)idx[v].size(); ++t) {
      b.push_back(-(idx[v][t] - (t ? idx[v][t - 1] : -1) - 1));
      b.push_back(1);
    }
    b.push_back(-(n - idx[v].back() - 1));
    DEBUG(b);
    reverse(begin(b), end(b));
    int t = n;
    st.set(t, {t, t});
    sum.set(t, {1, 1});
    for (int e : b) {
      if (e == 1) {
        ++t;
        res += sum.acc(0, t).v;
        st.set(t, {st.get(t).v + t, t});
        sum.set(t, {sum.get(t).v + 1, 1});
      } else {
        res += sum.acc(0, t + e).v * -e + sum.acc(t + e, t).v * (t - 1) - st.acc(t + e, t).v;
        st.act(t + e, t, 1);
        sum.act(t + e, t, 1);
        t += e;
      }
    }
    t = n;
    for (int e : b) {
      if (e == 1) {
        ++t;
        st.set(t, {st.get(t).v - t, t});
        sum.set(t, {sum.get(t).v - 1, 1});
      } else {
        st.act(t + e, t, -1);
        sum.act(t + e, t, -1);
        t += e;
      }
    }
  }
  cout << res << '\n';
}
0