fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //
  4. const int mx = 2e5 + 5;
  5. const int maxa = 1e6 + 5;
  6. const int S = 450;
  7. //
  8. struct query
  9. {
  10.     int l, r, id;
  11.     //
  12.     bool operator < (const query &other)
  13.     {
  14.         if (l / S != other.l / S)
  15.             return l < other.l;
  16.         return l / S & 1 ? r < other.r : r > other.r;
  17.     }
  18. };
  19. //
  20. int n, t, a[mx];
  21. int cnt[maxa];
  22. long long ans[mx];
  23. query Q[mx];
  24. //
  25. void calc (void)
  26. {
  27.     int l = 0, r = 0;
  28.     long long sum = 0;
  29.     //
  30.     for (int i = 1; i <= t; ++i)
  31.     {
  32.         while (l < Q[i].l)
  33.         {
  34.             --cnt[a[l]];
  35.             sum -= (cnt[a[l]] << 1 | 1LL) * a[l];
  36.             ++l;
  37.         }
  38.         while (l > Q[i].l)
  39.         {
  40.             --l;
  41.             sum += (cnt[a[l]] << 1 | 1LL) * a[l];
  42.             ++cnt[a[l]];
  43.         }
  44.         while (r < Q[i].r)
  45.         {
  46.             ++r;
  47.             sum += (cnt[a[r]] << 1 | 1LL) * a[r];
  48.             ++cnt[a[r]];
  49.         }
  50.         while (r > Q[i].r)
  51.         {
  52.             --cnt[a[r]];
  53.             sum -= (cnt[a[r]] << 1 | 1LL) * a[r];
  54.             --r;
  55.         }
  56.         ans[Q[i].id] = sum;
  57.     }
  58. }
  59. //
  60. void process (void)
  61. {
  62.     cin >> n >> t;
  63.     for (int i = 1; i <= n; ++i)
  64.         cin >> a[i];
  65.     for (int i = 1; i <= t; ++i)
  66.         cin >> Q[i].l >> Q[i].r,
  67.         Q[i].id = i;
  68.  
  69.     sort(Q + 1, Q + t + 1);
  70.     calc();
  71.  
  72.     for (int i = 1; i <= t; ++i)
  73.         cout << ans[i] << '\n';
  74. }
  75. //
  76. signed main (void)
  77. {
  78.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  79.     process();
  80. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/A1ioZW
https://c...content-available-to-author-only...s.com/contest/86/problem/D
language:
C++14 (gcc 8.3)
created:
11 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!