Submission #593154

#TimeUsernameProblemLanguageResultExecution timeMemory
593154SeDunionDiversity (CEOI21_diversity)C++17
0 / 100
1 ms340 KiB
#include <iostream> #include <cassert> #include <iomanip> #include <algorithm> #include <string> #include <bitset> #include <vector> #include <cmath> #include <deque> #include <queue> #include <stack> #include <map> #include <set> #ifndef LOCAL #include <bits/stdc++.h> #define cerr if(false)cerr #endif using namespace std; using ll = long long; const int N = 3e5 + 66; ll a[N], n; ll pref[N]; /* summa(a[i]*(a[i]+1)/2 + a[i]*pref[i-1]*(i+1) - a[i]*(pref[n-1]-pref[i])*i) summa((a[i]^2+a[i])/2 + a[i]*pref[i-1]*i+a[i]*pref[i-1] - a[i]*(pref[n-1]-pref[i])*i) summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i-a[i]^2*i + a[i]*pref[i-1] - a[i]*(pref[n-1]-pref[i])*i) summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i-a[i]^2*i + a[i]*pref[i]-a[i]^2 - a[i]*(pref[n-1]-pref[i])*i) summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i-a[i]^2*i + a[i]*pref[i]-a[i]^2 - a[i]*pref[n-1]*i - a[i]*pref[i]*i) summa((a[i]^2+a[i])/2 + a[i]*pref[i]*i - a[i]^2*i + a[i]*pref[i]-a[i]^2 - a[i]*pref[n-1]*i - a[i]*pref[i]*i) summa(a[i]/2 + a[i]*pref[i]*(i+1) - a[i]^2*i - a[i]^2/2 - a[i]*pref[n-1]*i - a[i]*pref[i]*i) summa(a[i]/2 + a[i]*pref[i] - a[i]^2*i - a[i]^2/2 - a[i]*pref[n-1]*i) summa(a[i]/2 + a[i]*pref[i] - a[i]^2*i - a[i]^2/2 - a[i]*pref[n-1]*i) */ ll f(ll s) { return s * (s + 1) / 2; } //summa(f(pref[i - 1]) + f(pref[n - 1] - pref[i])) ll solve() { ll ans = 0; for (int i = 0 ; i < n ; ++ i) { pref[i] = a[i]; if (i) pref[i] += pref[i - 1]; } for (int i = 0 ; i < n ; ++ i) { if (i) ans += f(pref[i - 1]); ans += f(pref[n - 1] - pref[i]); } ll C = n * f(pref[n-1]); // C = len * f(sum) return C-ans; } vector<int>vec; int used[N]; int comp[N], freq[N]; void del(int v) { v = a[v]; cerr << "del " << v << endl; comp[freq[v]]--; freq[v]--; if (freq[v] > 0 && !comp[freq[v]] && !used[freq[v]]) { used[freq[v]] = 1; vec.emplace_back(freq[v]); } comp[freq[v]]++; } void add(int v) { v = a[v]; cerr << "add " << v << endl; comp[freq[v]]--; freq[v]++; if (freq[v] > 0 && !comp[freq[v]] && !used[freq[v]]) { used[freq[v]] = 1; vec.emplace_back(freq[v]); } comp[freq[v]]++; } deque<ll>d; int L, R; ll get() { for (int i = 0 ; i < (int)vec.size() ; ++ i) { if (!comp[i]) { used[vec[i]] = 0; swap(vec[i], vec.back()); vec.pop_back(); --i; } } sort(vec.rbegin(), vec.rend()); ll q = 0; d.clear(); for (int i : vec) { for (int _ = 0 ; _ < comp[i] ; ++ _) { if ((int)d.size() & 1) d.push_back(i); else d.push_front(i); } } int m = d.size(); ll pref = 0; cerr << "m "; for (int i = 0 ; i < m ; ++ i) cerr << d[i] << " "; cerr << endl; for (int i = 0 ; i < m ; ++ i) { q -= f(pref) + f(R-L+1 - pref - d[i]); pref += d[i]; } q += m * f(R-L+1); cerr << "get " << q << endl; return q; } ll ans[N]; int ql[N], qr[N]; vector<tuple<int,int,int>>MO; const int K = 400; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int q; cin >> n >> q; for (int i = 0 ; i < n ; ++ i) cin >> a[i]; for (int i = 0 ; i < q ; ++ i) { cin >> ql[i] >> qr[i]; ql[i]--, qr[i]--; MO.emplace_back(ql[i]/K, qr[i], i); } sort(MO.begin(), MO.end()); L = 1, R = 0; for (int $ = 0 ; $ < q ; ++ $) { int i = get<2>(MO[$]); int l = ql[i], r = qr[i]; while (L > l) add(--L); while (R < r) add(++R); while (L < l) del(L++); while (R > r) del(R--); ans[i] = get(); } for (int i = 0 ; i < q ; ++ i) { cout << ans[i] << "\n"; } return 0; map<int,int>mp; for (int i = 0 ; i < n ; ++ i) mp[a[i]]++; vector<int>freq; for (auto [f, s] : mp) freq.emplace_back(s); sort(freq.rbegin(), freq.rend()); deque<int>p; for (int i : freq) { if ((int)p.size() & 1) p.push_back(i); else p.push_front(i); } n = p.size(); for (int i = 0 ; i < n ; ++ i) a[i] = p[i]; cout << solve(); }
#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...