#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define long unsigned long
#define pb push_back
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define lb lower_bound
#define ub upper_bound
#define sz(v) int((v).size())
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
const int MAXN = 3e5+7;
int64_t calc(int64_t n) {
return (n*(n+1)) >> 1;
}
int64_t calc2(int64_t n) {
return n*(n+1)*(2*n+1)/6;
}
struct MO {
vector <int> freq;
map <int, int> comp;
int N;
MO() {
N = 0;
freq.resize(MAXN);
}
void add(int n) {
if (freq[n]) comp[freq[n]]--;
freq[n]++;
comp[freq[n]]++;
N++;
}
void remove(int n) {
comp[freq[n]]--;
freq[n]--;
if (freq[n]) comp[freq[n]]++;
N--;
}
int64_t get() {
int saizu = 0;
deque <pii> K;
for (auto rit = comp.rbegin(); rit != comp.rend(); rit++) {
auto x = *rit;
if (saizu % 2 == 0) {
K.push_front(mp(x.first, (x.second+1) >> 1));
if (x.second > 1)
K.push_back(mp(x.first, x.second >> 1));
}
else {
if (x.second > 1)
K.push_front(mp(x.first, x.second >> 1));
K.push_back(mp(x.first, (x.second+1) >> 1));
}
saizu += x.second;
}
int64_t l = 0, r;
int64_t ans = 0;
for (auto p : K) {
int x = p.first, k = p.second;
r = N-l-x;
int64_t a = k*calc(x);
int64_t b = k*l + x*calc(k-1);
int64_t c = k*r - x*calc(k-1);
int64_t d = k*l*r + x*(r*calc(k-1) - l*calc(k-1) - x*calc2(k-1));
ans += a + b*x + c*x + d;
l += k*x;
}
return ans;
}
};
void solve() {
int n, q;
cin >> n >> q;
int BLOCK = sqrt(n);
vector <int> v(n);
vector <int64_t> ans(q);
vector <pair <pii, int>> queries(q);
for (int i = 0; i < n; i++) {
scanf("%d", &v[i]);
}
for (int i = 0; i < q; i++) {
scanf("%d%d", &queries[i].first.first, &queries[i].first.second);
//~ cin >> queries[i].first.first >> queries[i].first.second;
queries[i].first.first--;
queries[i].first.second--;
queries[i].second = i;
}
sort(all(queries), [&](pair <pii, int> a, pair <pii, int> b) {
if (a.first.first/BLOCK == b.first.first/BLOCK) {
return a.first.second < b.first.second;
}
return a.first.first/BLOCK < b.first.first/BLOCK;
});
int l = 0, r = -1;
MO mo;
for (auto to : queries) {
auto ql = to.first.first, qr = to.first.second, ind = to.second;
while (r < qr) {
r++;
mo.add(v[r]);
}
while (l > ql) {
l--;
mo.add(v[l]);
}
while (r > qr) {
mo.remove(v[r]);
r--;
}
while (l < ql) {
mo.remove(v[l]);
l++;
}
ans[ind] = mo.get();
}
for (auto to : ans) printf("%lld\n", to);
}
int main() {
do_not_disturb
int t = 1;
//~ cin >> t;
while (t--) {
solve();
}
return 0;
}
Compilation message
diversity.cpp: In function 'void solve()':
diversity.cpp:132:36: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'long int' [-Wformat=]
132 | for (auto to : ans) printf("%lld\n", to);
| ~~~^ ~~
| | |
| | long int
| long long int
| %ld
diversity.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &v[i]);
| ~~~~~^~~~~~~~~~~~~
diversity.cpp:97:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d%d", &queries[i].first.first, &queries[i].first.second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
