FHQ Treap

\(\text{FHQ Treap}\)是一种好写好用的平衡树。

它的平衡策略和普通\(\text{Treap}\)相似,采用在维护\(\text{BST}\)性质的同时维护随机的堆的形态来维持平衡;
但是维护结构的方式和\(\text{Treap}\)不同,不采用旋转,而是采用拆和合并的方法来维持树和堆的特性。

同时,由于\(\text{FHQ Treap}\)的操作所涉及的节点和基于旋转的其他平衡树相比少(仅\(\log n\)个),它支持可持久化

继续阅读“FHQ Treap”

bzoj刷题记录 (1)

1011: [HNOI2008]遥远的行星

利用题目特殊条件暴力+乱搞,详见文章

代码
/*
 DOCUMENT NAME "20181128-bnds1011.cpp"
 CREATION DATE 2018-11-28
 SIGNATURE CODE_20181128_BNDS1011
 COMMENT [HNOI2008]遥远的行星
*/

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;

template<typename IntType>
void read(IntType& val) {
    val = 0;
    int c;
    bool inv = false;
    while (!isdigit(c = getchar()))
        if (c == '-')
            inv = true;
    do {
        val = (val << 1) + (val << 3) + c - '0';
    } while (isdigit(c = getchar()));
    if (inv)
        val = -val;
}

typedef long long ll;
const int MaxN = 1e5 + 10;

int n;
double a;
int m[MaxN];
ll sum[MaxN];


int main(int argc, char* argv[]) {

    read(n);
    scanf("%lf", &a);

    for (int i = 1; i <= n; i++) {
        read(m[i]);
        sum[i] = sum[i - 1] + m[i];
    }

    for (int i = 1; i <= n; i++) {
        int fl = i * a + 1e-7;
        if (i <= 1000) {
            double ans = 0;
            for (int j = 1; j <= fl; j++)
                ans += (double)m[j] * m[i] / (i - j);
            printf("%lf\n", ans);
        } else
            printf("%lf\n", (double)sum[fl] * m[i] / (i - .5*fl));
    }

    return 0;
}

继续阅读“bzoj刷题记录 (1)”