素晴らしき日々

1
#include <bits/stdc++.h>
2

3
using namespace std;
4
#define int long long
5
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
6
#define x first
7
#define y second
8
#define endl "\n"
9
typedef signed long long LL;
10
typedef pair<int, int> PII;
11

12
const int N = 1e5 + 10;
13

14
class Node{
15
public:
16
    int l, r;
17
    int cnt, sum; // cnt 表示当前节点的子树中元素的个数， sum表示当前区间的元素和
18
};
19

20
Node tr[N * 4 + N * 18];
21
int n, m;
22
int dp[N], a[N];
23
int root[N], idx;
24
vector<int> nums;
25

26
int find(int x){
27
    return lower_bound(nums.begin(),nums.end(), x, greater<int>()) - nums.begin();
28
}
29

30
int build(int l, int r){
31
    int p = ++idx;
32
    if(l == r) {
33
        tr[p].cnt = tr[p].sum = 0;
34
        return p;
35
    }
36
    int mid = l + r >> 1;
37
    tr[p].l = build(l, mid), tr[p].r = build(mid + 1, r);
38
    tr[p].cnt = tr[p].sum = 0;
39
    return p;
40
}
41

42
int insert(int p, int l,int r, int x){
43
    int q = ++idx; //创建新节点
44
    tr[q] = tr[p]; //复制老节点
45
    if(l == r){ // 写错了, tr中的 l 和 r表示左右子树的指针, l, r才是左右端点
46
        tr[q].cnt++;
47
        tr[q].sum += nums[x];
48
        return q;
49
    }
50
    int mid = l + r >> 1;
51
    if(x <= mid) tr[q].l = insert(tr[p].l, l, mid , x ); //查找值在左半
52
    else tr[q].r = insert(tr[p].r, mid + 1, r, x); //查找值在右半
53
    tr[q].cnt = tr[tr[q].l].cnt + tr[tr[q].r].cnt;
54
    tr[q].sum = tr[tr[q].l].sum + tr[tr[q].r].sum;
55
    return q;
56
}
57

58
//所得到的就是 前 k 个最大的元素和
59
int query(int q, int p, int l, int r, int k){
60
    if(l == r)  return nums[l] * k; // 这里写错了，可能存在 k 小于 tr[q].cnt 的情况因此只能取剩余的k个
61
    int mid = l + r >> 1;
62
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; //计算左边区间数量
63
    if(cnt >= k) return query(tr[q].l, tr[p].l, l, mid, k);
64
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt) + tr[tr[q].l].sum - tr[tr[p].l].sum; // 左边元素和一定全部能加
65

66
}
67
void solve(){
68
    nums.clear();
69
    idx = 0;
70
    cin >> n;
71
    for(int i = 1; i <= n; i++) cin >> a[i], dp[i] = dp[i - 1] + i * i, nums.push_back(a[i]);
72
   sort(nums.begin(), nums.end(), greater<int>());
73
    nums.erase(unique(nums.begin(),nums.end()), nums.end());
74

75
    root[0] = build(0, nums.size() - 1);
76

77
    for(int i = 1; i <= n; i++){
78
        root[i] = insert(root[i - 1], 0, nums.size() - 1, find(a[i]));
79
    }
80

81
    cin >> m;
82
    while(m--){
83
        int l, r, k;
84
        cin >> l >> r >> k;
85
        //题目要求的是 以 ai 作为第一个 dp[mi][ki] 的值 dp的大小就是第 r - l + 1 个
86
        //在查找 前 k 个最大的元素和 时，需要注意的是，主席树维护的是区间内的数字数量和数字和
87
        cout << dp[r - l + 1] + query(root[r], root[l - 1], 0, nums.size() - 1, k) << endl;
88
    }
89
}
90

91
signed main(){
92
    IOS;
93
    int _;
94
    cin >> _;
95
    while(_--){
96
        solve();
97
    }
98
}

1
//所得到的就是 前 k 个最大的元素和
2
int query(int q, int p, int l, int r, int k){
3
    if(l == r)  return nums[l] * k; // 这里写错了，可能存在 k 小于 tr[q].cnt 的情况因此只能取剩余的k个
4
    int mid = l + r >> 1;
5
    int cnt = tr[tr[q].l].cnt - tr[tr[p].l].cnt; //计算左边区间数量
6
    if(cnt >= k) return query(tr[q].l, tr[p].l, l, mid, k);
7
    else return query(tr[q].r, tr[p].r, mid + 1, r, k - cnt) + tr[tr[q].l].sum - tr[tr[p].l].sum; // 左边元素和一定全部能加
8

9
}