高级数据结构|浙江省赛 —— E. Easy DP Problem（主席树、维护区间前K大值总和）算法|二分查找|线段树|数据结

TP
题意：

题意是一个逆天dp，告诉你是简单dp显然就不考dp了…
分析一下即可得知，每次给一段区间，询问区间前 K 大数的 sum 总和，再加上个i ? i i*i i?i 的区间总和。

思路：

很显然的裸的主席树维护。不止维护区间个数，还要维护区间 sum 值。查询的时候贪心一下，右区间能取满 K 个显然取右区间更优，否则右区间取满，剩下的左区间凑。

【高级数据结构|浙江省赛 —— E. Easy DP Problem（主席树、维护区间前K大值总和）】 C o d e : Code: Code:

#include #include #include #define mem(a,b) memset(a,b,sizeof a) #define cinios (ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)) #define forr(a,b,c) for(int a=b; a<=c; a++) #define all(a) a.begin(),a.end() #define oper(a) operator<(const a& ee)const #define endl "\n" #define ul (u << 1) #define ur (u << 1 | 1) using namespace std; typedef long long ll; typedef pair PII; const int N = 1e5 + 10, M = 100010, MM = 110; int INF = 0x3f3f3f3f, mod = 1e9 + 7; ll LNF = 0x3f3f3f3f3f3f3f3f; int n, m, k; int a[N]; ll qian[N]; vector vec; int find(int x) { return lower_bound(all(vec), x) - vec.begin() + 1; } struct tree { int l, r, cnt; ll sum; }tr[N * 30]; int root[N], idx; //主席树 —— 维护区间前 K 大值的 sumint build(int l, int r) { int p = ++idx, mid = l + r >> 1; if (l == r)return p; tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r); return p; } int update(int pre, int l, int r, int x) { int p = ++idx, mid = l + r >> 1; tr[p] = tr[pre]; tr[p].cnt++, tr[p].sum += vec[x - 1]; //此题可以直接在对信息有影响的路径上更改信息 if (l == r)return p; if (x <= mid)tr[p].l = update(tr[pre].l, l, mid, x); else tr[p].r = update(tr[pre].r, mid + 1, r, x); return p; }ll query(int p, int pre, int l, int r, int k) { if (l == r) { //到底后要注意拿 k 个即可 ll t = (tr[p].sum - tr[pre].sum) / ((ll)tr[p].cnt - tr[pre].cnt); return t * k; } int mid = l + r >> 1; int x = tr[tr[p].r].cnt - tr[tr[pre].r].cnt; //能拿右边拿右边，肯定 sum 更大 if (x >= k)return query(tr[p].r, tr[pre].r, mid + 1, r, k); //否则右边尽可能拿完，再在左边拿够 k - x 个 return query(tr[p].l, tr[pre].l, l, mid, k - x) + tr[tr[p].r].sum - tr[tr[pre].r].sum; //这样递归不是往左就是往右，时间肯定是二分的 log }void solve() { cin >> n; for (int i = 1; i <= idx; i++)//主席树的特别清空 tr[i] = { 0,0,0,0 }; idx = 0; vec.clear(); forr(i, 1, n)cin >> a[i], vec.push_back(a[i]); forr(i, 1, n) { qian[i] = qian[i - 1] + 1ll * i * i; } sort(all(vec)); vec.erase(unique(all(vec)), vec.end()); m = vec.size(); root[0] = build(1, m); for (int i = 1; i <= n; i++) root[i] = update(root[i - 1], 1, m, find(a[i])); int qq; cin >> qq; while (qq--) { int l, r, k; cin >> l >> r >> k; ll t = query(root[r], root[l - 1], 1, m, k); cout << t + qian[r - l + 1] << endl; } }signed main() { cinios; int T = 1; cin >> T; forr(t, 1, T) { solve(); } return 0; } /* 1 5 1 2 3 4 5 3 1 3 2 1 5 5 3 3 1 */