题意：从某个区间内最多选择k个数，使得和最大
思路：首先题目给定的数有负数，如果区间前k大出现负数，那么负数不选和更大，于是对于所有最优选择，负数不会出现，所以用0取代负数，问题便转化为区间的前k大数和。
划分树：
[1 6 3 8 5 4 7 2]
[6 8 5 7][1 3 4 2]
[8 7][6 5][3 4][1 2]
[8][7][6][5][4][3][2][1]
把快排的结果从上至下依次放入线段树，就构成了划分树，划分的意思就是选定一个数，把原序列分成两块，使得左边整体大于右边，而一个块内的数在原序列的相对位置不发生变化。划分树的过程基本就是初始化，建树，和查找。初始化只要把原序列导入划分树的根就行了，建树过程依赖排好序的原序列来得到用来“划分”的数，查找过程也很简单，不需要像线段树那样将询问分解，在树上查找答案的时候是左右子树二选一。
划分树一般用来求区间第k大数，对于划分树为什么可以求区间k大和，见代码。
1 #pragma comment(linker, "/STACK:10240000,10240000") 2 3 #include <iostream> 4 #include <cstdio> 5 #include <algorithm> 6 #include <cstdlib> 7 #include <cstring> 8 #include <map> 9 #include <queue> 10 #include <deque> 11 #include <cmath> 12 #include <vector> 13 #include <ctime> 14 #include <cctype> 15 #include <set> 16 #include <bitset> 17 #include <functional> 18 #include <numeric> 19 #include <stdexcept> 20 #include <utility> 21 22 using namespace std; 23 24 #define mem0(a) memset(a, 0, sizeof(a)) 25 #define mem_1(a) memset(a, -1, sizeof(a)) 26 #define lson l, m, rt << 1 27 #define rson m + 1, r, rt << 1 | 1 28 #define rep_up0(a, b) for (int a = 0; a < (b); a++) 29 #define rep_up1(a, b) for (int a = 1; a <= (b); a++) 30 #define rep_down0(a, b) for (int a = b - 1; a >= 0; a--) 31 #define rep_down1(a, b) for (int a = b; a > 0; a--) 32 #define all(a) (a).begin(), (a).end() 33 #define lowbit(x) ((x) & (-(x))) 34 #define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {} 35 #define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {} 36 #define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {} 37 #define pchr(a) putchar(a) 38 #define pstr(a) printf("%s", a) 39 #define sstr(a) scanf("%s", a) 40 #define sint(a) scanf("%d", &a) 41 #define sint2(a, b) scanf("%d%d", &a, &b) 42 #define sint3(a, b, c) scanf("%d%d%d", &a, &b, &c) 43 #define pint(a) printf("%d ", a) 44 #define test_print1(a) cout << "var1 = " << a << endl 45 #define test_print2(a, b) cout << "var1 = " << a << ", var2 = " << b << endl 46 #define test_print3(a, b, c) cout << "var1 = " << a << ", var2 = " << b << ", var3 = " << c << endl 47 #define mp(a, b) make_pair(a, b) 48 #define pb(a) push_back(a) 49 50 typedef unsigned int uint; 51 typedef long long LL; 52 typedef pair<int, int> pii; 53 typedef vector<int> vi; 54 55 const int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1}; 56 const int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1 }; 57 const int maxn = 1e4 + 17; 58 const int md = 1e9 + 7; 59 const int inf = 1e9 + 7; 60 const LL inf_L = 1e18 + 7; 61 const double pi = acos(-1.0); 62 const double eps = 1e-6; 63 64 template<class T>T gcd(T a, T b){return b==0?a:gcd(b,a%b);} 65 template<class T>bool max_update(T &a,const T &b){if(b>a){a = b; return true;}return false;} 66 template<class T>bool min_update(T &a,const T &b){if(b<a){a = b; return true;}return false;} 67 template<class T>T condition(bool f, T a, T b){return f?a:b;} 68 template<class T>void copy_arr(T a[], T b[], int n){rep_up0(i,n)a[i]=b[i];} 69 int make_id(int x, int y, int n) { return x * n + y; } 70 71 /// 划分树求区间前k大和 72 /// 关于为什么可以用前缀和来求前k大的和：对于一个询问区间，如果前k大在左子树， 73 /// 那么这k个数会按原顺序依次进入左子树，进入左子树后它们之间不会有其它不是前k大的数， 74 /// 所以对应到下一层也是连续的一段，于是可用前缀和来得到，对于前k大跨区间的情况同理。 75 /// 区间范围为：1 ~ n 76 struct PartitionTree { 77 int val[20][maxn], sum[20][maxn], cnt[20][maxn];//划分后的结果，前缀和，进入左子树的个数 78 void init(int a[], int l, int r) { 79 mem0(val); 80 mem0(sum); 81 mem0(cnt); 82 for (int i = l; i <= r; i ++) sum[0][i] = sum[0][i - 1] + (val[0][i] = a[i]); 83 } 84 /// 向下更新val和sum数组，同时维护cnt数组的值 85 void build(int b[], int l, int r, int dep) { 86 if (l == r) return ; 87 int m = (l + r) >> 1; 88 /// c记录大于中位数的数的个数，cc记录进入左子树的等于中位数的数的个数，由于相等情况的存在，这个信息必不可少。 89 int lc = 0, rc = 0, lt = (r - l + 2) >> 1, c = 0, cc = 0; 90 for (int i = l; i <= r; i ++) c += val[dep][i] > b[m]; 91 for (int i = l; i <= r; i ++) { 92 cnt[dep][i] = cnt[dep][i - 1]; 93 if (lc < lt && (val[dep][i] > b[m] || val[dep][i] == b[m] && cc < lt - c)) { 94 val[dep + 1][l + lc ++] = val[dep][i]; 95 cnt[dep][i] ++; 96 if (val[dep][i] == b[m]) cc ++; 97 } 98 else { 99 val[dep + 1][m + 1 + rc ++] = val[dep][i]; 100 } 101 } 102 103 for (int i = l; i <= r; i ++) sum[dep + 1][i] = sum[dep + 1][i - 1] + val[dep + 1][i]; 104 build(b, l, m, dep + 1); 105 build(b, m + 1, r, dep + 1); 106 } 107 int query_ksum(int L, int R, int k, int l, int r, int dep) { 108 if (k == 0) return 0; 109 if (l == r) return val[dep][l]; 110 int m = (l + r) >> 1, c = cnt[dep][R] - cnt[dep][L - 1]; 111 if (c >= k) { 112 int x = cnt[dep][L - 1] - cnt[dep][l - 1], y = cnt[dep][R] - cnt[dep][l - 1]; 113 return query_ksum(l + x, l + y - 1, k, l, m, dep + 1); 114 } 115 else { 116 int x0 = cnt[dep][L - 1] - cnt[dep][l - 1], x = L - l - cnt[dep][L - 1] + cnt[dep][l - 1], y = R - l + 1 - cnt[dep][R] + cnt[dep][l - 1]; 117 return sum[dep + 1][l + x0 - 1 + c] - sum[dep + 1][l + x0 - 1] + query_ksum(m + 1 + x, m + 1 + y - 1, k - c, m + 1, r, dep + 1); 118 } 119 } 120 121 }; 122 PartitionTree pt; 123 pii node[maxn]; 124 int a[maxn], b[maxn], p[maxn]; 125 126 bool cmp(int i, int j) { 127 return i > j; 128 } 129 int main() { 130 //freopen("in.txt", "r", stdin); 131 int n, m; 132 while (cin >> n) { 133 rep_up0(i, n) { 134 sint2(node[i].first, node[i].second); 135 max_update(node[i].second, 0); 136 } 137 sort(node, node + n); 138 rep_up0(i, n) { 139 b[i] = a[i] = node[i].second; 140 p[i] = node[i].first; 141 } 142 sort(b, b + n, cmp); 143 pt.init(a - 1, 1, n); 144 pt.build(b - 1, 1, n, 0); 145 cin >> m; 146 rep_up0(i, m) { 147 int l, r, k; 148 sint3(l, r, k); 149 l = lower_bound(p, p + n, l) - p + 1; 150 r = upper_bound(p, p + n, r) - p; 151 min_update(k, r - l + 1); 152 printf("%d ", pt.query_ksum(l, r, k, 1, n, 0)); 153 } 154 cout << endl; 155 } 156 return 0; 157 }