fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #ifdef LOCAL
  5. #define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
  6. #else
  7. #define DEBUG(...) 6
  8. #endif
  9.  
  10. template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
  11. template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
  12. ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
  13. template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
  14. template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
  15. if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}
  16.  
  17. struct Node {
  18.     int l, r;
  19.     bool flip = false;
  20.     long long sum = 0, hsum = 0, hlazy1 = 0, hlazy2 = 0, cnt = 0, ti = -1, lazyFirstTi = -1, lazyTi = -1;
  21.  
  22.     void leaf() {}
  23.  
  24.     void pull(const Node &a, const Node &b) {
  25.         sum = a.sum + b.sum;
  26.         ti = max(a.ti, b.ti);
  27.         hsum = a.hsum + b.hsum + (ti - a.ti) * a.sum + (ti - b.ti) * b.sum;
  28.     }
  29.  
  30.     void push(const Node &other) {
  31.         flip ^= other.flip;
  32.         if (cnt % 2 == 0) {
  33.             hlazy1 += other.hlazy1;
  34.             hlazy2 += other.hlazy2;
  35.         } else {
  36.             hlazy1 += other.hlazy2;
  37.             hlazy2 += other.hlazy1;
  38.         }
  39.         if (lazyTi == -1) {
  40.             lazyFirstTi = other.lazyFirstTi;
  41.         } else {
  42.             if (cnt % 2 == 0)
  43.                 hlazy2 += other.lazyFirstTi - lazyTi;
  44.             else
  45.                 hlazy1 += other.lazyFirstTi - lazyTi;
  46.         }
  47.         cnt += other.cnt;
  48.         lazyTi = other.lazyTi;
  49.     }
  50.  
  51.     void apply() {
  52.         hsum += hlazy1 * (r - l + 1 - sum) + (hlazy2 + lazyFirstTi - ti) * sum;
  53.         ti = lazyTi;
  54.         if (flip)
  55.             sum = r - l + 1 - sum;
  56.         flip = false;
  57.         hlazy1 = hlazy2 = cnt = 0;
  58.         lazyFirstTi = lazyTi = -1;
  59.     }
  60. };
  61.  
  62. struct SegmentTree {
  63.     int n;
  64.     vector<int> a;
  65.     vector<Node> st;
  66.  
  67.     SegmentTree(int _n) : n(_n), a(n), st(4*n) {
  68.         build(1, 0, n-1);
  69.     }
  70.  
  71.     SegmentTree(const vector<int> &_a) : n((int) _a.size()), a(_a), st(4*n) {
  72.         build(1, 0, n-1);
  73.     }
  74.  
  75.     void build(int p, int l, int r) {
  76.         st[p].l = l;
  77.         st[p].r = r;
  78.         if (l == r) {
  79.             st[p].leaf();
  80.             return;
  81.         }
  82.         int m = (l + r) / 2;
  83.         build(2*p, l, m);
  84.         build(2*p+1, m+1, r);
  85.         st[p].pull(st[2*p], st[2*p+1]);
  86.     }
  87.  
  88.     void push(int p) {
  89.         if (st[p].lazyTi != -1) {
  90.             if (st[p].l != st[p].r) {
  91.                 st[2*p].push(st[p]);
  92.                 st[2*p+1].push(st[p]);
  93.             }
  94.             st[p].apply();
  95.         }
  96.     }
  97.  
  98.     Node query(int p, int i, int j) {
  99.         push(p);
  100.         if (st[p].l == i && st[p].r == j)
  101.             return st[p];
  102.         int m = (st[p].l + st[p].r) / 2;
  103.         if (j <= m)
  104.             return query(2*p, i, j);
  105.         else if (i > m)
  106.             return query(2*p+1, i, j);
  107.         Node ret, ls = query(2*p, i, m), rs = query(2*p+1, m+1, j);
  108.         ret.pull(ls, rs);
  109.         return ret;
  110.     }
  111.  
  112.     long long query(int i, int j, long long ti) {
  113.         Node ret = query(1, i, j);
  114.         return ret.hsum + (ti - ret.ti) * ret.sum;
  115.     }
  116.  
  117.     void update(int p, int i, int j, int ti) {
  118.         if (st[p].l == i && st[p].r == j) {
  119.             Node cur;
  120.             cur.flip = true;
  121.             cur.cnt = 1;
  122.             cur.lazyFirstTi = cur.lazyTi = ti;
  123.             st[p].push(cur);
  124.             push(p);
  125.             return;
  126.         }
  127.         push(p);
  128.         int m = (st[p].l + st[p].r) / 2;
  129.         if (j <= m) {
  130.             update(2*p, i, j, ti);
  131.             push(2*p+1);
  132.         } else if (i > m) {
  133.             push(2*p);
  134.             update(2*p+1, i, j, ti);
  135.         } else {
  136.             update(2*p, i, m, ti);
  137.             update(2*p+1, m+1, j, ti);
  138.         }
  139.         st[p].pull(st[2*p], st[2*p+1]);
  140.     }
  141.  
  142.     void update(int i, int j, int ti) {
  143.         update(1, i, j, ti);
  144.     }
  145. };
  146.  
  147. int main() {
  148.     ios_base::sync_with_stdio(false);
  149.     cin.tie(NULL);
  150.  
  151.     int n;
  152.     cin >> n;
  153.     vector<int> a(n);
  154.     for (int i=0; i<n; i++) {
  155.         cin >> a[i];
  156.         a[i]--;
  157.     }
  158.     int m;
  159.     cin >> m;
  160.     vector<vector<pair<int, int>>> queries(n);
  161.     for (int i=0; i<m; i++) {
  162.         int l, r;
  163.         cin >> l >> r;
  164.         l--, r--;
  165.         queries[r].emplace_back(l, i);
  166.     }
  167.  
  168.     SegmentTree st(n);
  169.     vector<int> last(n, -1);
  170.     vector<long long> ret(m);
  171.     for (int r=0; r<n; r++) {
  172.         if (last[a[r]] != -1)
  173.             st.update(0, last[a[r]], r);
  174.         last[a[r]] = r;
  175.         st.update(0, r, r);
  176.         for (auto [l, i] : queries[r])
  177.             ret[i] = st.query(l, r, (long long) r + 1);
  178.     }
  179.  
  180.     for (long long x : ret)
  181.         cout << x << "\n";
  182.  
  183.     return 0;
  184. }
  185.  
Success #stdin #stdout 0.01s 5428KB
comments (?)
stdin
copy 
5
1 2 3 2 1
5
1 5
2 4
1 3
2 5
4 4
stdout
copy 
10
3
4
6
1
https://ideone.com/aADK7p
language:
C++14 (gcc 8.3)
created:
2 years 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!