제출 #1087327

#제출 시각아이디문제언어결과실행 시간메모리
1087327vladiliusDiversity (CEOI21_diversity)C++17
64 / 100
7059 ms11864 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{ ll bit[A + 1]; int n; FT(int ns){ n = ns; for (int i = 1; i <= n; i++) bit[i] = 0; } void upd(int v, ll 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 = 300; auto cmp = [&](arr3 x, arr3 y){ if (x[0] / S == y[0] / S){ return x[1] < y[1]; } return x[0] < y[0]; }; 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; vector<int> f(n + 1), cnt(A + 1); vector<int> :: iterator it; FT T1(n), T2(n); auto add = [&](int x){ x = a[x]; it = upper_bound(f.begin() + 1, f.end(), cnt[x]); it--; int j1 = (int) (it - f.begin()), j = p[j1]; sum += (f[j1] + 1); sum += (1LL * j * T1.get(1, j - 1)); sum -= (T2.get(1, j - 1) - T1.get(1, j - 1)); sum += T2.get(j + 1, n); sum -= 1LL * (j - 1) * T1.get(j + 1, n); cnt[x]++; f[j1]++; T1.upd(j, 1); T2.upd(j, j); }; auto rem = [&](int x){ x = a[x]; it = lower_bound(f.begin() + 1, f.end(), cnt[x]); int j1 = (int) (it - f.begin()), j = p[j1]; sum -= f[j1]; sum -= (1LL * j * T1.get(1, j - 1)); sum += (T2.get(1, j - 1) - T1.get(1, j - 1)); sum -= T2.get(j + 1, n); sum += 1LL * (j - 1) * T1.get(j + 1, n); cnt[x]--; f[j1]--; T1.upd(j, -1); T2.upd(j, -j); }; vector<ll> out(q + 1); int lc = 1, rc = 0; for (auto [l, r, ii]: qs){ while (lc < l) rem(lc++); while (lc > l) add(--lc); while (rc < r) add(++rc); 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...