是treap常数大了，还是我写丑了？

Waddles @ 2019-10-31 22:28:31

by 权御天下 @ 2019-10-31 22:52:08

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int ans;
struct node
{
    int data, siz, rp;
    node *ch[2];
    node(int a = 0)
    {
        data = a;
        ch[0] = ch[1] = NULL;
        siz = 1;
        rp = rand()*rand();
    }
    void maintain()
    {
        siz = 1;
        if (ch[0] != NULL)
            siz += ch[0]->siz;
        if (ch[1] != NULL)
            siz += ch[1]->siz;
    }
};
node *root;

class treap
{
private:
    void split(int x, node *bt, node *&lfr, node *&rfr)
    {
        if (bt == NULL)
        {
            lfr = rfr = NULL;
            return;
        }
        if (x >= bt->data)
        {
            lfr = bt;
            split(x, bt->ch[1], bt->ch[1], rfr);
        }
        else
        {
            rfr = bt;
            rfr = bt, split(x, bt->ch[0], lfr, bt->ch[0]);
        }
        bt->maintain();
    }
    void merge(node *&bt, node *a, node *b)
    {
        if (a == NULL || b == NULL)
        {
            bt = (a == NULL ? b : a);
            return;
        }
        if (a->rp < b->rp)
        {
            bt = a;
            merge(bt->ch[1], bt->ch[1], b);
        }
        else
        {
            bt = b;
            merge(bt->ch[0], a, bt->ch[0]);
        }
        bt->maintain();
    }
public:
    treap()
    {
        root = NULL;
    }
    void insert(int x)
    {
        node *a = NULL, *b = NULL, *c = new node(x);
        split(x, root, a, b);
        merge(a, a, c);
        merge(root, a, b);
    }
    void remove(int x)
    {
        node *a = NULL, *b = NULL, *c = NULL;
        split(x, root, a, b);
        split(x - 1, a, a, c);
        merge(c, c->ch[0], c->ch[1]);
        merge(a, a, c);
        merge(root, a, b);
    }
    int kth(int x, node *bt = root)
    {
        while (1)
        {
            if (bt == NULL)
                return 0;
            int s = 0;
            if (bt->ch[0] != NULL)
                s += bt->ch[0]->siz;
            if (s + 1 == x)
                break;
            if (s >= x)
                bt = bt->ch[0];
            else
            {
                x -= s + 1;
                bt = bt->ch[1];
            }
        }
        return bt->data;
    }
};
treap tr;
int n, m, e;
int x[2000010], d;
int main()
{
    scanf("%d%d", &n, &m);
    printf("0\n");
    for(register int i = 1; i < n; ++i){
        scanf("%d", &x[i]);
        tr.insert(x[i]);
        if(e >= m)
            tr.remove(x[++d]);
        else
            ++e;
        printf("%d\n", tr.kth(1));
    }
    return 0;
}

是不是我也丑了awa

by 孤独を見守る @ 2019-10-31 22:52:08

@静谧时空 拜拜

by 小菜鸟 @ 2019-10-31 22:52:54

@AT是女孩子 另外没有用profiler纯靠yy和道听途说的优化都不靠谱...

by Magallan_forever @ 2019-10-31 22:53:14

@小菜鸟 可是这都是在luogu上评测啊除非他像wys那样卡常

by Waddles @ 2019-10-31 22:54:08

@守望孤独 这个题能用动规写，tql

by Waddles @ 2019-10-31 22:54:34

@权御天下 本来是想练下手的，结果崩了

by Magallan_forever @ 2019-10-31 22:55:04

@小菜鸟 数组那个吗？我们教练说的，多开一个又不会MLE他说是底层实现的问题，我个人认为最好不要乱搞这些，如果CCF少爷机出锅就……了

by 小菜鸟 @ 2019-10-31 22:55:31

@AT是女孩子 ...感觉很多人听说的常数优化都不靠谱

比如快读写x*10实测比(x<<1)+(x<<3)快，c-48也比c^48快（

by 孤独を見守る @ 2019-10-31 22:56:10

@Song_of_long_voyage 自己看算法标签嘛

by 小菜鸟 @ 2019-10-31 22:56:32

@AT是女孩子 强推-pg+gprof联合食用，卡常好帮手