fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using PII = pair<ll, ll>;
  5. #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
  6. #define REP(i, n) FOR(i, 0, n)
  7. #define ALL(x) x.begin(), x.end()
  8. template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }
  9. template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }
  10. struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;
  11. #ifdef DEBUG_ 
  12. #include "../program_contest_library/memo/dump.hpp"
  13. #else
  14. #define dump(...)
  15. #endif
  16. const ll INF = 1LL<<30;
  17.  
  18. template <typename S>
  19. struct sparseTable {
  20.     using T = typename S::T;
  21.     int n;
  22.     vector<int> log2;
  23.     vector<vector<T>> t;
  24.  
  25.     sparseTable() {}
  26.     sparseTable(int nn) { construct(nn); }
  27.     void construct(int nn) {
  28.         n = nn;
  29.         log2.assign(n+1, 0);
  30.         for(int i=2; i<=n; ++i) log2[i] = log2[i >> 1] + 1;
  31.         t = vector<vector<T>>(log2[n]+1, vector<T>(n));
  32.     }
  33.     void init(vector<T> v) {
  34.         for(int i=0; i<n; ++i) t[0][i] = v[i];
  35.         for(int j=1; j<=log2[n]; ++j) {
  36.             int w = 1LL<<(j-1);
  37.             for (int i = 0; i+(w<<1) <= n; ++i) {
  38.                 t[j][i] = S::op(t[j-1][i], t[j-1][i+w]);
  39.             }
  40.         }
  41.     }
  42.     // [l, r]
  43.     T query(int l, int r) {
  44.         int j = log2[r - l];
  45.         return S::op(t[j][l], t[j][r-(1 << j)+1]);
  46.     }
  47. };
  48.  
  49. class LCA {
  50. private:
  51.     const int n = 0;
  52.     const int log2_n = 0;
  53.     vector<vector<int>> par;
  54.     vector<vector<int>> g;
  55.     vector<int> depth;     // 頂点iの深さ
  56.     vector<int> vs;        // 頂点を訪問順に並べたもの
  57.     vector<int> depth_seq; // depth_seq[i] = (頂点vs[i]の深さ)
  58.     vector<int> id;        // 頂点が初めてvsに登場するインデックス
  59.     struct minimum_st {
  60.         using T = PII;
  61.         static T op(const T& a, const T& b) { return min(a, b); }
  62.     }; 
  63.     sparseTable<minimum_st> st;
  64.     void dfs(int v, int p, int d, int &k) {
  65.         id[v] = k; vs[k] = v; depth_seq[k++] = d; depth[v] = d;
  66.         for(auto to: g[v]) if(to != p) {
  67.             dfs(to, v, d+1, k);
  68.             vs[k] = v; depth_seq[k++] = d;
  69.         }
  70.     }
  71. public:
  72.     LCA(int n_=1e5) : n(n_), g(n), depth(n), vs(2*n-1), depth_seq(2*n-1), id(n) {}
  73.     // u-vに辺を張る
  74.     void add_edge(int u, int v) {
  75.         g[u].push_back(v);
  76.         g[v].push_back(u);
  77.     }
  78.     // rootを根として初期化
  79.     void build(int root = 0) {
  80.         int k = 0;
  81.         dfs(root, -1, 0, k);
  82.         vector<PII> v(2*n-1);
  83.         REP(i, 2*n-1) v[i] = {depth_seq[i], i};
  84.         st.construct(2*n-1);
  85.         st.init(v);
  86.     }
  87.     // uとvのlcaを返す O(1)
  88.     int get(int u, int v) {
  89.         if(id[u] > id[v]) swap(u, v);
  90.         return vs[st.query(id[u], id[v]).second];
  91.     }
  92.     int dist(int u, int v) {
  93.         return depth[u] + depth[v] - 2*depth[get(u,v)];
  94.     }
  95. };
  96.  
  97. int main(void) {
  98.     int n;
  99.     cin >> n;
  100.     vector<int> a(n);
  101.     REP(i, n) cin >> a[i], a[i]--;
  102.  
  103.     // 二分探索木をつくる
  104.     LCA lca(n);
  105.     vector<vector<int>> g(n);
  106.     {
  107.         set<int> st;
  108.         vector<int> lch(n, -1), rch(n, -1);
  109.  
  110.         st.insert(a[0]);      
  111.         FOR(i, 1, n) {
  112.             // a[i] が追加される位置
  113.             // a[i]以上の最小の要素の左の子
  114.             // a[i]未満の最大の要素の右の子
  115.  
  116.             auto itr = st.lower_bound(a[i]);
  117.             if(itr != st.begin() && rch[*prev(itr)] == -1) {
  118.                 rch[*prev(itr)] = a[i];
  119.             } else if(itr != st.end() && lch[*itr] == -1) {
  120.                 lch[*itr] = a[i];
  121.             }
  122.             st.insert(a[i]);
  123.         }
  124.  
  125.         auto dfs = [&](auto &&self, int v) -> void {
  126.             if(lch[v] != -1) {
  127.                 g[v].push_back(lch[v]);
  128.                 g[lch[v]].push_back(v);
  129.                 lca.add_edge(v, lch[v]);
  130.                 self(self, lch[v]);
  131.             }
  132.             if(rch[v] != -1) {
  133.                 g[v].push_back(rch[v]);
  134.                 g[rch[v]].push_back(v);
  135.                 lca.add_edge(v, rch[v]);
  136.                 self(self, rch[v]);
  137.             }
  138.         };
  139.         dfs(dfs, a[0]);
  140.         lca.build();
  141.     }
  142.  
  143.     vector<int> sz(n), dead(n);
  144.     auto find_centroid = [&](int root) {
  145.         auto get_size = [&](auto &&self, int v, int p) -> void {
  146.             sz[v] = 1;
  147.             for(auto to: g[v]) if(to != p && !dead[to]) {
  148.                 self(self, to, v);
  149.                 sz[v] += sz[to];
  150.             }
  151.         };
  152.         get_size(get_size, root, -1);
  153.         auto dfs = [&](auto &&self, int v, int p) -> int {
  154.             for(auto to: g[v]) if(to != p && !dead[to]) {
  155.                 if(sz[to] > sz[root]/2) return self(self, to, v);
  156.             }
  157.             return v;
  158.         };
  159.         return dfs(dfs, root, -1);
  160.     };
  161.  
  162.     vector<int> par(n);
  163.     auto centroid_decomposition = [&](auto &&self, int root, int p) -> void {
  164.         int c = find_centroid(root);
  165.         dead[c] = true;
  166.         par[c] = p;
  167.         for(auto to: g[c]) if(!dead[to]) {
  168.             self(self, to, c);
  169.         }
  170.         dead[c] = false;
  171.     };
  172.     centroid_decomposition(centroid_decomposition, 0, -1);
  173.  
  174.     ll ret = 0;
  175.     vector<ll> dist(n), contribution(n), cnt(n);
  176.     REP(i, n) {
  177.         {
  178.             int v = a[i];
  179.             ll add = dist[a[i]];
  180.             while(par[v] != -1) {
  181.                 add += dist[par[v]]-contribution[v] + (cnt[par[v]]-cnt[v]) * lca.dist(par[v], a[i]);
  182.                 v = par[v];
  183.             }
  184.             ret += add;
  185.             cout << ret << "\n";
  186.         }
  187.         {
  188.             int v = par[a[i]], pre = a[i];
  189.             cnt[a[i]]++;
  190.             while(v != -1) {
  191.                 cnt[v]++;
  192.                 const ll d = lca.dist(v, a[i]);
  193.                 dist[v] += d;
  194.                 contribution[pre] += d;
  195.                 pre = v;
  196.                 v = par[v];
  197.             }
  198.         }
  199.     }
  200.     cout << flush;
  201.  
  202.     return 0;
  203. }
Runtime error #stdin #stdout #stderr 0s 4384KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/JiLYK8
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!