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

发表于 | 分类于 | | + s

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、维护值域
对于这个区间比某数大的，要想到在值域开线段树/树状数组

#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;
}
------ 本文结束 ------