treap模版

发布于 2017-12-13  12 次阅读


#include 
#include 
#include 
using namespace std;
#define N 20005
struct tree
{
    int key, prio, size, son[2];
}t[N];
int ans[N], root = 0, cnt = 1;
void push_up(int x)
{
    t[x].size = t[t[x].son[0]].size + t[t[x].son[1]].size + 1;
}
void rotate(int p, int &x)
{
    int y = t[x].son[!p];
    t[x].son[!p] = t[y].son[p];
    t[y].son[p] = x;
    push_up(x);
    push_up(y);
    x = y;
}
void insert(int key, int &x)
{
    if (x == 0)
        t[x = cnt++] = (tree) {key, rand(), 1, {0, 0}};
        else
        {
            t[x].size++;
            int p = key <= t[x].key;
            insert(key, t[x].son[!p]);
            if (t[x].prio > t[t[x].son[!p]].prio)
                rotate(p, x);
        }  
}
int find(int key, int x)
{
    if (x == 0) return 0;
    else if (t[x].key <= key)
        return t[t[x].son[0]].size + 1 + find(key, t[x].son[1]);
    else find(key, t[x].son[0]);
}
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        ans[find(x, root)]++;
        insert(x, root);
    }
    for (int i = 0; i <= n - 1; i++)
        printf("%d\n", ans[i]);
    return 0;
}
View Code

 

]]>