Submission #1234139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234139		Matthewwww	Diversity (CEOI21_diversity)	C++17	64 / 100	7091 ms	26704 KiB

diversity

#pragma GCC optimize("O3", "fast-math")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#ifdef LOCAL
#define err cerr
#else
#define err if (0) cerr
#endif
 
const int sq = 760;
 
struct node {
	ll l, r, v, t, e;
	node(): l(0), r(0), v(0), t(0), e(1) {}
	node (ll x): l(x), r(x), v(x*(x+1)/2), t(x), e(1) {}
	node operator+ (node b) {
		node c;
		c.l = l+b.l+e*b.t;
		c.r = r+b.r+b.e*t;
		c.v = v+b.v+t*b.l+b.t*r;
		c.t = t+b.t;
		c.e = e+b.e;
		return c;
	}
};
 
struct Sgt {
	int n;
	vector<node> vt;
	Sgt (int N): n(N), vt(2*N) {}
	void update (int i, int x) {
		i += n;
		vt[i] = node(vt[i].t+x);
		while (i >>= 1) vt[i] = vt[i<<1]+vt[i<<1|1];
	}
};
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, q;
	cin >> n >> q;
	vector<int> vt(n);
	for (int &i: vt) cin >> i;
	vector<int> cc(vt.begin(), vt.end());
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	for (int &i: vt) i = lower_bound(cc.begin(), cc.end(), i)-cc.begin();
	int m = 1<<(int)log2(cc.size()*2);
	vector<int> cnt(m, 0);
	Sgt *sgt[2];
	sgt[0] = new Sgt(m/2);
	sgt[1] = new Sgt(m/2);
	vector<pair<int, int>> st(n+9);
	st[0] = {0, m};
	for (int i = 1; i < n+9; i++) st[i] = {m, m};
	vector<pair<int, int>> qs(q);
	for (auto &i: qs) {
		cin >> i.f >> i.s;
		i.f--;
	}
	vector<vector<int>> bucket(n/sq+1);
	for (int i = 0; i < q; i++) bucket[qs[i].f/sq].push_back(i);
	for (auto &i: bucket) sort(i.begin(), i.end(), [&](int a, int b) { return qs[a].s < qs[b].s;});
	vector<int> ord;
	vector<ll> ans(q);
	for (auto i: bucket) for (int j: i) ord.push_back(j);
	int l = 0, r = 0;
	auto rmv = [&](int i) {
		sgt[st[cnt[i]].f%2]->update(st[cnt[i]].f/2, -1);
		st[cnt[i]].f++;
		st[--cnt[i]].s++;
	};
	auto add = [&](int i) {
		sgt[(st[cnt[i]].s-1)%2]->update((st[cnt[i]].s-1)/2, 1);
		st[cnt[i]].s--;
		st[++cnt[i]].f--;
	};
	for (int i: ord) {
		auto p = qs[i];
		while (r < p.s) add(vt[r++]);
		while (l > p.f) add(vt[--l]);
		while (l < p.f) rmv(vt[l++]);
		while (r > p.s) rmv(vt[--r]);
		ans[i] = sgt[0]->vt[1].v+sgt[1]->vt[1].v+sgt[0]->vt[1].t*sgt[1]->vt[1].r+sgt[1]->vt[1].t*sgt[0]->vt[1].r;
	}
	for (ll i: ans) cout << i << "\n";
}
 
// no llama :(
// i miss you

• Subtask 1: 4 / 4
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 26 / 26
• Subtask 6: 0 / 36