Submission #1089981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089981		juicy	Diversity (CEOI21_diversity)	C++17	100 / 100	993 ms	6092 KiB

diversity

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5, B = 550;

int n, q;
int a[N], cnt[N], fre[N];
long long res[N];
vector<int> hev;

void add(int x, int y) {
  --fre[cnt[x]];
  ++fre[cnt[x] += y];
}

long long S1(int i) {
  return (long long) i * (i + 1) / 2;
}

long long S2(int i) {
  return (long long) i * (i + 1) * (2 * i + 1) / 6; 
}

long long calc(int i, int a, int b, int n) {
  return (long long) a * i * (n - i) + S1(a - 1) * b * (n - 2 * i) - S2(a - 1) * b * b;
}

long long qry(int l) {
  long long res = S1(l);
  vector<array<int, 2>> cnd;
  for (int i = 1; i < B; ++i) {
    if (fre[i]) {
      cnd.push_back({i, fre[i]});
    }
  }
  for (int i : hev) {
    if (cnt[i] >= B) {
      cnd.push_back({cnt[i], 1});
    }
  }
  sort(cnd.begin(), cnd.end());
  int x = 0, y = l, m = 0;
  for (auto [a, b] : cnd) {
    int lt, rt;
    if (m & 1) {
      lt = (b + 1) / 2;
      rt = b / 2;
    } else {
      lt = b / 2;
      rt = (b + 1) / 2;
    }
    if (lt) {
      res += calc(x, lt, a, l);
      x += lt * a;
    }
    if (rt) {
      y -= rt * a;
      res += calc(y, rt, a, l);
    }
    m += b;
  }
  return res;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    add(a[i], 1);
  }
  for (int i = 1; i < N; ++i) {
    if (cnt[i] >= B) {
      hev.push_back(i);
    }
  }
  vector<array<int, 3>> que;
  for (int i = 1; i <= q; ++i) {
    int l, r; cin >> l >> r;
    que.push_back({l, r, i});
  }
  sort(que.begin(), que.end(), [&](const auto &a, const auto &b) {
    return a[0] / B == b[0] / B ? a[1] < b[1] : a[0] < b[0];
  });
  int L = 1, R = n;
  for (auto [l, r, id] : que) {
    while (R < r) {
      add(a[++R], 1);
    } 
    while (L > l) {
      add(a[--L], 1);
    }
    while (R > r) {
      add(a[R--], -1);
    }
    while (L < l) {
      add(a[L++], -1);
    }
    res[id] = qry(r - l + 1);
  }
  for (int i = 1; i <= q; ++i) {
    cout << res[i] << "\n";
  }
  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 36 / 36