fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. using ll = long long;
  6. const int MOD = 1000000007;
  7. const int MOD2 = 998244353;
  8. const ll INF = 1e18;
  9. const int MX = 1000001; // check the limits, dummy
  10.  
  11. // Modular arithmetic utilities
  12. ll modExp(ll base, ll power) {
  13.     if (power == 0) {
  14.         return 1;
  15.     } else {
  16.         ll cur = modExp(base, power / 2);
  17.         cur = (cur * cur) % MOD;
  18.         if (power % 2 == 1) cur = (cur * base) % MOD;
  19.         return cur;
  20.     }
  21. }
  22.  
  23. ll inv(ll base) {
  24.     return modExp(base, MOD - 2);
  25. }
  26.  
  27. ll mul(ll A, ll B) {
  28.     return (A * B) % MOD;
  29. }
  30.  
  31. ll add(ll A, ll B) {
  32.     return (A + B) % MOD;
  33. }
  34.  
  35. ll dvd(ll A, ll B) {
  36.     return mul(A, inv(B));
  37. }
  38.  
  39. ll sub(ll A, ll B) {
  40.     return (A - B + MOD) % MOD;
  41. }
  42.  
  43. ll* facs = new ll[MX];
  44. ll* facInvs = new ll[MX];
  45.  
  46. ll choose(ll a, ll b) {
  47.     if (b > a || a < 0 || b < 0) return 0;
  48.     ll cur = facs[a];
  49.     cur = mul(cur, facInvs[b]);
  50.     cur = mul(cur, facInvs[a - b]);
  51.     return cur;
  52. }
  53.  
  54. void initFacs() {
  55.     facs[0] = 1;
  56.     facInvs[0] = 1;
  57.     for (int i = 1; i < MX; i++) {
  58.         facs[i] = (facs[i - 1] * i) % MOD;
  59.         facInvs[i] = inv(facs[i]);
  60.     }
  61. }
  62.  
  63. // --------------------
  64. // Mo's Algorithm setup
  65. // --------------------
  66.  
  67. // A Query stores [l, r] (0-indexed) and its original index
  68. struct Query {
  69.     int l, r, idx, block;
  70. };
  71.  
  72. // Comparator for sorting queries in Mo's order
  73. bool mo_cmp(const Query& A, const Query& B) {
  74.     if (A.block != B.block)
  75.         return A.block < B.block;
  76.     return (A.block & 1) ? (A.r > B.r) : (A.r < B.r);
  77. }
  78.  
  79. // Global / static variables for Mo's
  80. static int BLOCK_SIZE;
  81. vector<int> arr;
  82. ll currentAnswer = 0;
  83.  
  84. // Example frequency array; adjust size if necessary
  85. // If arr[i] can be up to 1e6, size it accordingly.
  86. static const int MAXV = 1000001;
  87. static int freq[MAXV];
  88.  
  89.  
  90.  
  91. void add(int pos) {
  92.     int x = arr[pos];
  93.     int prevcount = freq[x];
  94.  
  95.     currentAnswer -= (prevcount * prevcount) * x;
  96.  
  97.     freq[x] ++;
  98.  
  99.     int newcount = freq[x];
  100.     currentAnswer += (newcount * newcount) * x;
  101.  
  102. }
  103.  
  104. // Remove element at position pos from the current window
  105. void remove_(int pos) {
  106.     int x = arr[pos];
  107.     int prevcount = freq[x];
  108.  
  109.     currentAnswer -= (prevcount * prevcount) * x;
  110.  
  111.     freq[x] --;
  112.  
  113.     int newcount = freq[x];
  114.     currentAnswer += (newcount * newcount) * x;
  115.  
  116.  
  117. }
  118.  
  119. int main() {
  120.     ios_base::sync_with_stdio(false);
  121.     cin.tie(nullptr);
  122.  
  123.     initFacs(); // If you plan to use choose(), etc.
  124.  
  125.     int n, m, k;
  126.     cin >> n >> m >> k;
  127.     arr.resize(n);
  128.     for (int i = 0; i < n; i++) {
  129.         cin >> arr[i];
  130.     }
  131.  
  132.     // Build queries
  133.     vector<Query> qs(m);
  134.     BLOCK_SIZE = static_cast<int>(sqrt(n));
  135.     for (int i = 0; i < m; i++) {
  136.         int l, r;
  137.         cin >> l >> r;
  138.         --l; --r; // convert to 0-based
  139.         qs[i] = {l, r, i, l / BLOCK_SIZE};
  140.     }
  141.  
  142.     sort(qs.begin(), qs.end(), mo_cmp);
  143.  
  144.     vector<ll> answers(m);
  145.     int currL = 0, currR = -1;
  146.     currentAnswer = 0;
  147.     memset(freq, 0, sizeof(freq));
  148.  
  149.     for (auto& q : qs) {
  150.         int L = q.l;
  151.         int R = q.r;
  152.         while (currL > L) {
  153.             add(--currL);
  154.         }
  155.         while (currR < R) {
  156.             add(++currR);
  157.         }
  158.         while (currL < L) {
  159.             remove_(currL++);
  160.         }
  161.         while (currR > R) {
  162.             remove_(currR--);
  163.         }
  164.         answers[q.idx] = currentAnswer;
  165.     }
  166.  
  167.     // Output answers in original order
  168.     for (int i = 0; i < m; i++) {
  169.         cout << answers[i] << "\n";
  170.     }
  171.  
  172.     return 0;
  173. }
  174.  
Success #stdin #stdout 0.23s 23236KB
comments (?)
stdin
copy 
8 3
1 1 2 2 1 3 1 1
2 7
1 6
2 7
stdout
copy 
15
6
9
https://ideone.com/ewgWnk
language:
C++ (gcc 8.3)
created:
4 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!