Codeforces 1042D(权值树状数组+前缀和/非旋Treap+前缀和)

Codeforces 1042D
题意:给出一个序列,求出有多少个区间满足区间和小于$t$。
解:先处理前缀和$pre$,对于题目$pre_r-pre_l < t$成立即可。移项$pre_r-t < pre_l$,那么只需要检查$[1,i)$中的$pre_i$有多少个大于$pre_r-t$即可,右边不取因为前缀和的定义。这里方便没有将$l$写作$l-1$。可以取反做,也可以正着做。
然后就是求$[1,i)$有多少个大于$x$的数了。这个如果直接维护序列下标很难求,我们可以用树状数组维护值域,然后询问区间和就行了,但是要离散化。这题也可以维护下标,用一个平衡树求 $rk$ 即可。
知识点:对于区间维护,可以有两种形式
1、维护序列下标
2、维护值域
对于这个区间比某数大的,要想到在值域开线段树/树状数组

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const LL MAXN = 200000 + 5;
struct Treap *null, *pit, *root;//自建的null节点,内存池指针
struct Treap {
LL key, val, s;//键值(满足排序二叉树性质),附加值(满足堆性质),以本节点为根的子树大小
Treap *lc, *rc;//Treap 左右结点
Treap() {};
void init(LL key) {this->key = key, val = rand(), lc = rc = null, s = 1;}//初始化
void maintain() {s = lc->s + rc->s + 1;}//更新,维护以本节点为根的子树大小
}pool[MAXN];//内存池
Treap* newNode(LL key) {
pit->init(key);
return pit++;
}
Treap* merge(Treap *a, Treap *b) {//合并两棵Treap,所有key(a)<key(b)才能合并,为了满足排序二叉树性质
if (a == null) return b;
if (b == null) return a;
if (a->val < b->val) {
a->rc = merge(a->rc, b), a->maintain();
//a小自然a要在b的上面,满足堆性质
return a;
}
if (a->val >= b->val) {
b->lc = merge(a, b->lc), b->maintain();
//a大自然a要在b的下面,满足堆性质
return b;
}
}
void split_v(Treap *o, LL v, Treap *&x, Treap *&y) {//用权值分开一棵Treap,分开的第一棵根为x,第二棵根为y。x,y可以称为左右子树“下一个”位置,也就是如果还有满足左边的,就放在x或者y的位置
if (o == null) x = y = null; else {
if (o->key <= v) {
x = o, split_v(o->rc, v, o->rc, y);//x = o说明o左边全部放进x,递归右子树
} else y = o, split_v(o->lc, v, x, o->lc);
o->maintain();
}
}
void split_k(Treap *o, LL k, Treap *&x, Treap *&y) {//按前k个分配分开一棵Treap,分开的第一棵根为x,第二棵根为y。x,y可以称为左右子树“下一个”位置,也就是如果还有满足左边的,就放在x或者y的位置
if (o == null) x = y = null; else {
if (k <= o->lc->s) {
y = o, split_k(o->lc, k, x, o->lc);//y = o说明o右边全部放进y,递归左子树
} else x = o, split_k(o->rc, k - o->lc->s - 1, o->rc, y);
o->maintain();
}
}
void insert(LL v) {//插入一个数
Treap *a, *b;
split_v(root, v, a, b);
root = merge(merge(a, newNode(v)), b);
}
void del(LL v) {//删除一个数
Treap *a, *b;
split_v(root, v, a, b);
Treap *c, *d;
split_v(a, v - 1, c, d);
d = merge(d->lc, d->rc);
a = merge(c, d), root = merge(a, b);
}
LL kth(LL k) {//查询排名为k的数
Treap *a, *b;
split_k(root, k - 1, a, b);
Treap *c, *d;
split_k(b, 1, c, d);
LL ret = c->key;
b = merge(c, d), root = merge(a, b);
return ret;
}
LL rk(LL x) {//查询x的排名
Treap *a, *b;
split_v(root, x, a, b);
LL ret = a->s;
root = merge(a, b);
return ret;
}
LL pre(LL x) {//求x的前驱
Treap *a, *b;
split_v(root, x - 1, a, b);
Treap *c, *d;
split_k(a, a->s - 1, c, d);
LL ret = d->key;
a = merge(c, d), root = merge(a, b);
return ret;
}
LL succ(LL x) {//求x的后继
Treap *a, *b;
split_v(root, x, a, b);
Treap *c, *d;
split_k(b, 1, c, d);
LL ret = c->key;
b = merge(c, d), root = merge(a, b);
return ret;
}
void initTreap() {
srand(19660813);//置随机数种子
pit = pool;//指针指向内存池
null = newNode(0), null->s = 0;//初始化自建的null节点
root = null;//初始化树根
}
LL n, t, pr[200000 + 5];
void clean() {}
void solve() {
clean();
initTreap();
scanf("%lld%lld", &n, &t); pr[0] = 0;
insert(pr[0]);
LL ans = 0;
for (LL x, i = 1; i <= n; i++) {
scanf("%lld", &x), pr[i] = pr[i - 1] + x;
ans += rk(pr[i] - t);
insert(pr[i]);
}
printf("%lld\n", 1ll * n * (n + 1) / 2 - ans);
}
int main() {
solve();
return 0;
}
------ 本文结束 ------