可持久化线段树
区间求前K大和
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 3; ll n, m, a[maxn]; vector <ll> v; struct node { ll l, r, sum; ll t; }T[maxn * 40]; int getid(ll x) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } ll cnt = 0; ll root[maxn]; void build(ll &rt, ll l, ll r) { rt = ++cnt; T[rt].sum = 0; T[rt].t = 0; if (l == r) return; ll mid = (l + r) / 2; build(T[rt].l, l, mid); build(T[rt].r, mid + 1, r); } void updata(ll l, ll r, ll &now, ll last, ll k) { T[++cnt] = T[last]; now = cnt; T[now].sum++; T[now].t += v[k - 1]; if (l == r) return; ll mid = (l + r) / 2; if (k <= mid) updata(l, mid, T[now].l, T[last].l, k); else updata(mid + 1, r, T[now].r, T[last].r, k); } ll query(ll l, ll r, ll x, ll y, ll k) { if (l == r) return (T[y].t - T[x].t) / (T[y].sum - T[x].sum) * k; ll ans = 0; ll mid = (l + r) / 2; ll tmp = T[T[y].r].sum - T[T[x].r].sum; if (tmp >= k) ans += query(mid + 1, r, T[x].r, T[y].r, k); else ans = query(l, mid, T[x].l, T[y].l, k - tmp) + T[T[y].r].t - T[T[x].r].t; return ans; } int main() { int Case; scanf("%d", &Case); while (Case--) { memset(root, 0, sizeof(root)); v.clear(); cnt = 0; scanf("%lld", &n); for (int i = 1; i <= n; i++) { scanf("%lld", a + i); v.push_back(a[i]); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); build(root[0], 1, n); for (int i = 1; i <= n; i++) updata(1, n, root[i], root[i - 1], getid(a[i])); scanf("%lld", &m); while (m--) { ll x, y, k; scanf("%lld%lld%lld", &x, &y, &k); ll p = y - x + 1; printf("%lld\n", (p * (p + 1) * (2 * p + 1) / 6) + query(1, n, root[x - 1], root[y], k)); } } return 0; }