fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. const int MAXN = 200005; // Max number of elements
  9. const int MAXVAL = 1000005; // Max value of elements
  10.  
  11. int n, t;
  12. long long a[MAXN];
  13. long long cnt[MAXVAL]; // Frequency count array
  14. long long current_ans = 0;
  15. long long answers[MAXN]; // Store results to print in correct order
  16. int BLOCK_SIZE;
  17.  
  18. struct Query {
  19.     int l, r, id;
  20.  
  21.     // Compare function for Mo's ordering
  22.     bool operator<(const Query& other) const {
  23.         int block_l = l / BLOCK_SIZE;
  24.         int block_other = other.l / BLOCK_SIZE;
  25.  
  26.         if (block_l != block_other)
  27.             return block_l < block_other;
  28.  
  29.         // Zigzag optimization: If block is odd, r increases; if block is even, r decreases
  30.         return (block_l % 2 == 0) ? (r < other.r) : (r > other.r);
  31.     }
  32. };
  33.  
  34. void add(int pos) {
  35.     long long val = a[pos];
  36.     long long delta = (2 * cnt[val] + 1) * val;
  37.     current_ans += delta;
  38.     cnt[val]++;
  39. }
  40.  
  41. void remove(int pos) {
  42.     long long val = a[pos];
  43.     long long delta = (2 * cnt[val] - 1) * val;
  44.     current_ans -= delta;
  45.     cnt[val]--;
  46. }
  47.  
  48. int main() {
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.  
  52.     if (!(cin >> n >> t)) return 0;
  53.  
  54.     // Calculate block size
  55.     BLOCK_SIZE = sqrt(n);
  56.  
  57.     for (int i = 1; i <= n; i++) {
  58.         cin >> a[i];
  59.     }
  60.  
  61.     vector<Query> queries(t);
  62.     for (int i = 0; i < t; i++) {
  63.         cin >> queries[i].l >> queries[i].r;
  64.         queries[i].id = i;
  65.     }
  66.  
  67.     // Sort queries according to Mo's order
  68.     sort(queries.begin(), queries.end());
  69.  
  70.     int curL = 1;
  71.     int curR = 0;
  72.     for (const auto& q : queries) {
  73.         // Increase or decrease R
  74.         while (curR < q.r) add(++curR);
  75.         while (curR > q.r) remove(curR--);
  76.  
  77.         // Increase or decrease L
  78.         while (curL < q.l) remove(curL++);
  79.         while (curL > q.l) add(--curL);
  80.  
  81.         answers[q.id] = current_ans;
  82.     }
  83.  
  84.     for (int i = 0; i < t; i++) {
  85.         cout << answers[i] << "\n";
  86.     }
  87.  
  88.     return 0;
  89. }
Success #stdin #stdout 0s 5640KB
comments (?)
stdin
copy 
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
stdout
copy 
20
20
20
https://ideone.com/gcC7QD
language:
C++ (gcc 8.3)
created:
2 days 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!