Submission #1087387

#TimeUsernameProblemLanguageResultExecution timeMemory
1087387vladiliusDiversity (CEOI21_diversity)C++17
100 / 100
5235 ms20976 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") using namespace std; using ll = long long; using pii = pair<int, int>; #define pb push_back #define ff first #define ss second #define ins insert #define arr3 array<int, 3> const int A = 3e5; struct FT{ ll bit[A + 1], a[A + 1], s; int n; FT(int ns){ n = ns; for (int i = 1; i <= n; i++){ bit[i] = a[i] = 0; } s = 0; } void upd(int v, ll x){ s += x; a[v] += x; while (v <= n){ bit[v] += x; v |= (v + 1); } } ll get(int v){ ll out = 0; while (v > 0){ out += bit[v]; v = (v & (v + 1)) - 1; } return out; } ll get(int l, int r){ if (l > r) return 0; return get(r) - get(l - 1); } }; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin>>n>>q; vector<int> a(n + 1); for (int i = 1; i <= n; i++){ cin>>a[i]; } vector<arr3> qs; for (int i = 1; i <= q; i++){ int l, r; cin>>l>>r; qs.pb({l, r, i}); } const int S = sqrt(n); auto cmp = [&](arr3 x, arr3 y){ int x1 = x[0] / S, y1 = y[0] / S; if (x1 != y1){ return x[0] < y[0]; } return (x1 & 1) ? (x[1] < y[1]) : (x[1] > y[1]); }; sort(qs.begin(), qs.end(), cmp); vector<int> p(n + 1); for (int i = 1; i <= n; i++){ if (i % 2){ p[i] = (i + 1) / 2; } else { p[i] = n - i / 2 + 1; } } ll sum = 0, s1, s2; vector<int> f(n + 1), cnt(A + 1); pii rr[n + 1]; rr[0] = {1, n}; for (int i = 1; i <= n; i++) rr[i] = {0, 0}; FT T1(n), T2(n); auto add = [&](int x){ x = a[x]; int k = cnt[x], j1 = rr[k].ss, j = p[j1]; sum += (f[j1] + 1); s1 = T1.get(1, j - 1); s2 = T2.get(1, j - 1); sum += (1LL * j * s1); sum -= (s2 - s1); sum += (T2.s - s2 - T2.a[j]); sum -= 1LL * (j - 1) * (T1.s - s1 - T1.a[j]); if (rr[k].ff == rr[k].ss) rr[k] = {0, 0}; else rr[k].ss--; cnt[x]++; f[j1]++; k++; T1.upd(j, 1); T2.upd(j, j); if (!rr[k].ff) rr[k] = {j1, j1}; else rr[k].ff--; }; auto rem = [&](int x){ x = a[x]; int k = cnt[x], j1 = rr[k].ff, j = p[j1]; sum -= f[j1]; s1 = T1.get(1, j - 1); s2 = T2.get(1, j - 1); sum -= (1LL * j * s1); sum += (s2 - s1); sum -= (T2.s - s2 - T2.a[j]); sum += 1LL * (j - 1) * (T1.s - s1 - T1.a[j]); if (rr[k].ff == rr[k].ss) rr[k] = {0, 0}; else rr[k].ff++; cnt[x]--; f[j1]--; k--; T1.upd(j, -1); T2.upd(j, -j); if (!rr[k].ff) rr[k] = {j1, j1}; else rr[k].ss++; }; vector<ll> out(q + 1); int lc = 1, rc = 0; for (auto [l, r, ii]: qs){ while (lc > l) add(--lc); while (rc < r) add(++rc); while (lc < l) rem(lc++); while (rc > r) rem(rc--); out[ii] = sum; } for (int i = 1; i <= q; i++){ cout<<out[i]<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...