fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5.  
  6. using namespace std;
  7.  
  8. struct Segment_Tree
  9. {
  10.     struct Node
  11.     {
  12.         int l, r;
  13.         ll sum, lazy, sum_mul;
  14.  
  15.         Node(int l = 0, int r = 0, ll sum = 0, ll lazy = 0, ll sum_mul = 0) :
  16.             sum(sum), lazy(lazy), sum_mul(sum_mul) {};
  17.         bool operator == (const Node &other) const
  18.         {
  19.             return sum == other.sum && lazy == other.lazy && sum_mul == other.sum_mul;
  20.         }
  21.     };
  22.  
  23.     int n;
  24.     vector<Node> tree;
  25.     Node nll;
  26.  
  27.     Segment_Tree(int n = 0) : n(n)
  28.     {
  29.         nll = Node(-1e9, -1e9, -1e18, -1e18, -1e18);
  30.         tree.assign(4 * n + 10, Node(0, 0, 0, 0, 0));
  31.     }
  32.     void update_node(Node &a, int l, int r, ll val)
  33.     {
  34.         ll len = r - l + 1;
  35.         a.l = l;
  36.         a.r = r;
  37.         a.sum += len * val;
  38.         a.lazy += val;
  39.         a.sum_mul += (len + 1) * len / 2 * val;
  40.     }
  41.     void push(int id, int l, int r)
  42.     {
  43.         if (tree[id].lazy == 0)
  44.             return ;
  45.         int m = l + r >> 1;
  46.         update_node(tree[id << 1], l, m, tree[id].lazy);
  47.         update_node(tree[id << 1 | 1], m + 1, r, tree[id].lazy);
  48.         tree[id].lazy = 0;
  49.     }
  50.     Node merge_node(Node a, Node b, int l, int r)
  51.     {
  52.         if (a == nll)
  53.             return b;
  54.         if (b == nll)
  55.             return a;
  56.         Node ans;
  57.         ans.sum = a.sum + b.sum;
  58.         ans.lazy = 0;
  59.         ans.sum_mul = a.sum_mul + (b.r - b.l + 1) * a.sum + b.sum_mul;
  60.         ans.l = a.l;
  61.         ans.r = b.r;
  62.         return ans;
  63.     }
  64.     void update(int id, int l, int r, int u, int v, ll val)
  65.     {
  66.         if (r < u || l > v)
  67.             return ;
  68.         if (u <= l && r <= v)
  69.         {
  70.             update_node(tree[id], l, r, val);
  71.             return ;
  72.         }
  73.         int m = l + r >> 1;
  74.         push(id, l, r);
  75.         update(id << 1, l, m, u, v, val);
  76.         update(id << 1 | 1, m + 1, r, u, v, val);
  77.         tree[id] = merge_node(tree[id << 1], tree[id << 1 | 1], l, r);
  78.     }
  79.     Node get(int id, int l, int r, int u, int v)
  80.     {
  81.         if (r < u || l > v)
  82.             return nll;
  83.         if (u <= l && r <= v)
  84.         {
  85. //            cout << l << ' ' << r << ' ' << tree[id].sum << ' ' << tree[id].sum_mul, el;
  86.             return tree[id];
  87.         }
  88.         int m = l + r >> 1;
  89.         push(id, l, r);
  90.         Node a = get(id << 1, l, m, u, v);
  91.         Node b = get(id << 1 | 1, m + 1, r, u, v);
  92.          return merge_node(a, b, l, r);
  93.     }
  94.     void update(int l, int r, ll val)
  95.     {
  96.         if (r < l)
  97.             return ;
  98.         update(1, 1, n, l, r, val);
  99.     }
  100.     Node get(int l, int r)
  101.     {
  102.         if (r < l)
  103.             return Node(0, 0, 0);
  104.         return get(1, 1, n, l, r);
  105.     }
  106. };
  107.  
  108. const int maxn = 2e5;
  109.  
  110. int n, a[maxn + 10];
  111. ll ans = 0;
  112. vector<int> v, pos[maxn + 10];
  113. Segment_Tree st;
  114.  
  115. int get_id(int x)
  116. {
  117.     return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
  118. }
  119.  
  120. int main()
  121. {
  122.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  123.     if (fopen("VBAUCU.INP", "r"))
  124.     {
  125.         freopen("VBAUCU.INP", "r", stdin);
  126.         freopen("VBAUCU.OUT", "w", stdout);
  127.     }
  128.  
  129.     cin >> n;
  130.     for (int i = 1; i <= n; i++)
  131.     {
  132.         cin >> a[i];
  133.         v.push_back(a[i]);
  134.     }
  135.     sort(v.begin(), v.end());
  136.     v.resize(unique(v.begin(), v.end()) - v.begin());
  137.     for (int i = 1; i <= n; i++)
  138.     {
  139.         a[i] = get_id(a[i]);
  140.         if (pos[a[i]].size() == 0)
  141.             pos[a[i]].push_back(1);
  142.         pos[a[i]].push_back(i);
  143.     }
  144.     st = Segment_Tree(2 * n + 2);
  145.     st.update(n + 1, n + 1, 1);
  146.  
  147.     for (int i = 1; i <= v.size(); i++)
  148.     {
  149. //        cout << i, el;
  150.         pos[i].push_back(n + 1);
  151.         for (int j = 1; j < pos[i].size(); j++)
  152.         {
  153.             int pre_l = -pos[i][j - 1] + 2 * (j - 1) + n + 1;
  154.             int pre_r = -(pos[i][j] - 1) + 2 * (j - 1) + n + 1;
  155.             int len = pos[i][j] - pos[i][j - 1];
  156.             if (pos[i][j - 1] > pos[i][j] - 1)
  157.                 continue;
  158.             int x = st.get(1, pre_r - 1).sum * len + st.get(pre_r, pre_l - 1).sum_mul;
  159.             ans += x;
  160. //            cout << pos[i][j - 1] << ' ' << pos[i][j] - 1 << ' ' << pre_l << ' ' << pre_r << ' ' << x, el;
  161.             st.update(pre_r, pre_l, 1);
  162.         }
  163. //        cout << ans, el;
  164.         for (int j = 1; j < pos[i].size(); j++)
  165.         {
  166.             ll pre_l = -pos[i][j - 1] + 2 * (j - 1) + n + 1;
  167.             ll pre_r = -(pos[i][j] - 1) + 2 * (j - 1) + n + 1;
  168.  
  169.             if (pos[i][j - 1] > pos[i][j] - 1)
  170.                 continue;
  171.             st.update(pre_r, pre_l, -1);
  172.         }
  173.     }
  174.     cout << ans;
  175. }
  176.  
Success #stdin #stdout 0.01s 8400KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D0plWu
language:
C++14 (gcc 8.3)
created:
6 hours ago
visibility:
public

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!