C -?Division

思路：我們考慮到一點，從大往小取得順序是不會有問題的，所以可以直接主席樹，但是開不下空間，我們可以log分段求。

#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std;const int N = 1e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const double eps = 1e-8;int n, q, all, hs[2 * N], hcnt, a[N], bin[31]; LL ans[5 * N], sum[N], csum[N]; pair<PII, int> qus[5 * N]; vector<int> vc[30][N];int root[2 * N], tot;struct node {LL sum;int cnt, ls, rs; } o[2 * N * 20];void update(int p, int l, int r, int &x, int y) {x = ++tot;o[x] = o[y];o[x].sum += p;o[x].cnt++;if(l == r) return;int mid = l + r >> 1;if(p <= hs[mid]) update(p, l, mid, o[x].ls, o[y].ls);else update(p, mid + 1, r, o[x].rs, o[y].rs); }LL query(int res, int l, int r, int x, int y) {if(o[x].cnt - o[y].cnt <= res) return o[x].sum - o[y].sum;if(l == r) return 1ll * res * hs[l];int mid = l + r >> 1, cntr = o[o[x].rs].cnt - o[o[y].rs].cnt;if(cntr >= res) return query(res, mid + 1, r, o[x].rs, o[y].rs);else return o[o[x].rs].sum - o[o[y].rs].sum + query(res-cntr, l, mid, o[x].ls, o[y].ls); }int main() {for(int i = bin[0] = 1; i <= 30; i++) bin[i] = bin[i - 1] << 1;scanf("%d%d", &n, &q);for(int i = 1; i <= n; i++) scanf("%d", &a[i]), sum[i] = sum[i - 1] + a[i];for(int i = 1; i <= q; i++) {scanf("%d%d%d", &qus[i].fi.fi, &qus[i].fi.se, &qus[i].se);ans[i] = sum[qus[i].fi.se] - sum[qus[i].fi.fi - 1];}for(int i = 1, j = 29; i <= n; i++, j = 29) {while(a[i]) {int val = a[i] - a[i] / 2;while(val < bin[j]) j--;vc[j][i].push_back(val);a[i] /= 2;}}for(int k = 29; k >= 0; k--) {tot = 0; hcnt = 0; all = 0;for(int i = 1; i <= n; i++) csum[i] = csum[i - 1] + SZ(vc[k][i]);if(!csum[n]) continue;for(int i = 1; i <= n; i++) for(auto& t : vc[k][i]) hs[++hcnt] = t;sort(hs + 1, hs + 1 + hcnt); hcnt = unique(hs + 1, hs + 1 + hcnt) - hs - 1;for(int i = 1; i <= n; i++) for(auto& t : vc[k][i]) update(t, 1, hcnt, root[all + 1], root[all]), all++;for(int i = 1; i <= q; i++) {if(!qus[i].se) continue;int L = qus[i].fi.fi, R = qus[i].fi.se, has = csum[R] - csum[L - 1];if(has >= qus[i].se) {ans[i] -= query(qus[i].se, 1, hcnt, root[csum[R]], root[csum[L - 1]]);qus[i].se = 0;} else {ans[i] -= query(has, 1, hcnt, root[csum[R]], root[csum[L - 1]]);qus[i].se -= has;}}}for(int i = 1; i <= q; i++) printf("%lld\n", ans[i]);return 0; }/* */ View Code

?

轉載于:https://www.cnblogs.com/CJLHY/p/10348134.html

總結

以上是生活随笔為你收集整理的2019 CCPC wannfly winter camp Day 5的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。