1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94
| #include<bits/stdc++.h> using namespace std; #define ll long long #define MAXN maxn #define per(a,b,c) for(int a=b;a<c;++a) #define rep(a,b,c) for(int a=c-1;a>=b;--a) int T,n,m; const int MAXN(500010); ll b[MAXN], summ[MAXN << 2], ptnm[MAXN << 2]; ll outt[MAXN], tmpp;
struct nd{ ll val, no; }a[MAXN];
void PushUp(int rt) { summ[rt] = summ[rt << 1] + summ[rt << 1 | 1]; ptnm[rt] = ptnm[rt << 1] + ptnm[rt << 1 | 1]; }
void Build(int l, int r, int rt) { if (l == r) { summ[rt] = a[l].val; ptnm[rt] = 1; return; } int mid = (l + r) >> 1; Build(l, mid, rt << 1); Build(mid + 1, r, rt << 1 | 1); PushUp(rt); }
void Add(int L, ll C, int l, int r, int rt) { if (l == r) { summ[rt] -= C; ptnm[rt]--; return; } int mid = (l + r) >> 1; if (L <= mid) { summ[rt] -= C; ptnm[rt]--; Add(L, C, l, mid, rt << 1); } else { summ[rt] -= C; ptnm[rt]--; Add(L, C, mid + 1, r, rt << 1 | 1); } }
int Query(ll C, int l, int r, int rt) { if(C<=0) return 0; if (l==r) return 1; int mid = (l + r) >> 1, ls=(rt<<1), rs=(rt<<1|1); if (summ[ls] > C) { return Query(C, l, mid, ls); } else { return ptnm[ls]+Query(C-summ[ls], mid + 1, r, rs); } }
int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>T; while(T--){ cin >> n >> m; tmpp = 0; per(i, 1, n+1) { cin >> a[i].val; a[i].no=i; tmpp+=a[i].val; } sort(a+1, a+1+n, [](const nd& a, const nd& b) {return a.val>b.val;}); per(i, 1, n+1) { b[a[i].no]=i; } tmpp-=m; Build(1, n, 1); rep(i, 1, n+1) { Add(b[i], a[b[i]].val, 1, n, 1); outt[i] = Query(tmpp, 1, n, 1); tmpp -= a[b[i]].val; } per(i, 1, n+1) { cout << outt[i] << " "; } cout << "\n"; } return 0; }
|