Submission #993789

#TimeUsernameProblemLanguageResultExecution timeMemory
993789vladiliusDiversity (CEOI21_diversity)C++17
0 / 100
2 ms3932 KiB
#include <bits/stdc++.h> 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{ vector<ll> bit; int n; FT(int ns){ n = ns; bit.resize(n + 1); } void upd(int p, int k){ // a[p] += k while (p <= n){ bit[p] += k; p |= (p + 1); } } ll get(int v){ // a[1] + ... + a[v] ll out = 0; while (v > 0){ out += bit[v]; v = (v & (v + 1)) - 1; } return out; } }; 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> all; for (int i = 1; i <= q; i++){ int l, r; cin>>l>>r; all.pb({l, r, i}); } const int sz = sqrt(n); auto cmp = [&](arr3& x, arr3& y){ if (x[0] / sz == x[1] / sz){ return x[1] < y[1]; } return x[0] < y[0]; }; sort(all.begin(), all.end(), cmp); ll sum = 0; int m = 0; vector<int> cnt(A + 1); /* for (int i = 1; i <= n; i++){ out += 1LL * x[i] * (1LL * i * sum - pr); sum += x[i]; pr += 1LL * (i - 1) * x[i]; } */ auto pp = [&](int p){ if (p % 2){ return p / 2 + 1; } return m - p / 2 + 1; }; // 1, 2, 1, 3, 2 FT Ts(n), Tp(n), T(A); auto add = [&](int i){ if (!i) return; // cout<<"add "<<i<<"\n"; int k = cnt[a[i]]; sum += (k + 1); int p, p1; if (!k){ p = p1 = m + 1; } else { p = (int) T.get(k); p1 = pp(p); } // cout<<"Yo "<<k<<" "<<p<<"\n"; // cout<<Ts.get(p - 1)<<" "<<Tp.get(p - 1)<<"\n"; sum += (1LL * (p1 + 1) * Ts.get(p1 - 1) - Tp.get(p1 - 1)); sum += (Tp.get(n) - Tp.get(p1)) - 1LL * (p1 - 1) * (Ts.get(n) - Ts.get(p1)); Ts.upd(p1, -k); Ts.upd(p1, (k + 1)); Tp.upd(p1, -1LL * p1 * k); Tp.upd(p1, 1LL * p1 * (k + 1)); if (k) T.upd(k, -1); else m++; cnt[a[i]]++; k++; T.upd(k, 1); }; // 1, 2, 2 auto rem = [&](int i){ if (!i) return; int k = cnt[a[i]]; sum -= k; int p, p1; if (k == 1){ p = p1 = m; } else { p = (int) T.get(k - 1) + 1; p1 = pp(p); } sum -= (1LL * (p1 + 1) * Ts.get(p1 - 1) - Tp.get(p1 - 1)); sum -= (Tp.get(n) - Tp.get(p1)) - 1LL * (p1 - 1) * (Ts.get(n) - Ts.get(p1)); Ts.upd(p1, -k); Ts.upd(p1, (k - 1)); Tp.upd(p1, -1LL * p1 * k); Tp.upd(p1, 1LL * p1 * (k - 1)); T.upd(k, -1); cnt[a[i]]--; k--; if (!k) m--; else T.upd(k, 1); }; vector<ll> out(q + 1); int lc = 0, rc = 0; for (int i = 0; i < q; i++){ auto &[l, r, ii] = all[i]; 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...