20190828模拟赛T3

发表于 更新于 分类于

$Problem’s$ $Website$

20190828模拟赛T3

$Solution$

首先，不懂权值线段树的同学可以暂时先去这学习一下。

根据数据范围，我们要离散化一下。

离散化之后，我们从$1$到$n$循环，每次输出 前面的元素个数 $-$ 已经合法的元素个数，即输出$i - 1 - query(1, 1, n, m - a[i])$，最后将当前的数据加到线段树上。

$Code$

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc getchar()
#define pc(x) putchar(x)
inline int sc() { 
    int xx = 0, ff = 1; char cch = gc;
    while(!isdigit(cch)) {
        if(cch == '-') ff = -1; cch = gc;
    }
    while(isdigit(cch)) {
        xx = (xx << 1) + (xx << 3) +(cch ^ '0'); cch = gc;
    }
    return xx * ff;
}
inline void out(int x) {
    if(x < 0)
        pc('-'), x = -x;
    if(x >= 10)
        out(x / 10);
    pc(x % 10 + '0');
}
using std :: sort;
using std :: pair;
using std :: make_pair;
#define P pair <int, int>
const int Maxn = 2e5 + 10;
int t, n, m;
int a[Maxn], c[Maxn];
P b[Maxn];
int rank[Maxn << 2];
long long val[Maxn << 2];
inline bool cmp(P x, P y) {
   if(x.second == y.second)
      return x.first < y.first;
    return x.second < y.second; 
}
inline void modify(int k, int l, int r, int x, int z) {
    if(l == r && l == x) {
        rank[k] += 1;
        val[k] += z;
        return;
    }
    int mid = l + r >> 1;
    if(x <= mid)
        modify(k << 1, l, mid, x, z);
    else
        modify(k << 1 | 1, mid + 1, r, x, z);
    rank[k] = rank[k << 1] + rank[k << 1 | 1];
    val[k] = val[k << 1] + val[k << 1 | 1];
}
inline int query(int k, int l, int r, int x) {
    if(val[k] <= x)
        return rank[k];
    if(l == r)
        return 0;
    int mid = l + r >> 1;
    if(val[k << 1] < x)
        return rank[k << 1] + query(k << 1 | 1, mid + 1, r, x - val[k << 1]);
    else
        return query(k << 1, l, mid, x);
}
#define re register
int main() {
    t = sc();
    while(t--) {
        memset(val, 0, sizeof(val));
        memset(rank, 0, sizeof(rank));
        n = sc(), m = sc();
        for(re int i = 1; i <= n; ++i) {
            a[i] = sc(), b[i] = make_pair(i, a[i]);
        }
        sort(b + 1, b + n + 1, cmp);
        for(re int i = 1; i <= n; ++i)
            c[b[i].first] = i;
        for(re int i = 1; i <= n; ++i) { 
            out(i - 1 - query(1, 1, n, m - a[i])), pc(' ');
            modify(1, 1, n, c[i], a[i]);
        }
        pc('\n');
    }
    return 0;
}

$rp++$