BZOJ3196: Tyvj 1730 二逼平衡树
treap 树套树 线段树 二分答案    2016-12-24 21:12:39    240    -1    0

3196: Tyvj 1730 二逼平衡树

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 3104  Solved: 1233
[Submit][Status][Discuss]

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

Solution

线段树套treap

treap调了好久。。药丸

 

操作二是二分答案做的。。log3好虚啊

应该有更加优美的做法吧。。

 

Source code

/*{{{*/
#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

typedef long long ll;
typedef std::pair<int, int> pii;

std::string Name = __FILE__;
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }

template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}
 
template <class T> inline void write(T x, const char p = '\n')
{
    static int top;
    static int s[30];
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    do s[++ top] = x % 10 + 48;
    while (x /= 10);
    while (top)
        putchar(s[top --]);
    putchar(p);
}
/*}}}*/
 
const int maxn = 50000 + 5;

inline int Rand()
{
    static int i;
    return i += 1234567891;
}

struct node
{
    int v, l, r, size, key, cnt;

    node() { }
    node(int val) { l = r = 0; key = Rand(); v = val; size = cnt = 1; }

} s[maxn * 25];

int tot;

struct Treap 
{
    int root;

    Treap() { root = 0; }

    void update(int x)
    {
        s[x].size = s[s[x].l].size + s[x].cnt + s[s[x].r].size;
    }

    void turn_right(int &x)
    {
        int now = s[x].l;
        s[x].l = s[now].r;
        s[now].r = x;
        update(x);
        update(x = now);
    }

    void turn_left(int &x)
    {
        int now = s[x].r;
        s[x].r = s[now].l;
        s[now].l = x;
        update(x);
        update(x = now);
    }

    void _Insert(int &x, int v)
    {
        if (!x) {
            x = ++ tot;
            s[x] = node(v);
            return;
        }

        ++ s[x].size;

        if (v == s[x].v)
            ++ s[x].cnt;
        else if (v < s[x].v) {
            _Insert(s[x].l, v);
            if (s[s[x].l].key < s[x].key)
                turn_right(x);
        } else {
            _Insert(s[x].r, v);
            if (s[s[x].r].key < s[x].key)
                turn_left(x);
        }
    }

    void Insert(int v)
    {
        _Insert(root, v);
    }

    void Delete(int &x, int v)
    {
        if(s[x].v == v) {
            if (s[x].cnt > 1) { 
                -- s[x].cnt;
                -- s[x].size;
                return; 
            }
            if (!s[x].l || !s[x].r)
                x = s[x].l + s[x].r;
            else if (s[s[x].l].key < s[s[x].r].key) {
                turn_right(x);
                Delete(x, v);
            } else {
                turn_left(x);
                Delete(x, v);
            }
            return;
        }
        else if (v < s[x].v)
            Delete(s[x].l, v);
        else
            Delete(s[x].r, v);
        -- s[x].size;
    }

    int pre(int v)
    {
        int p = root;
        int ret = -1;
        while (p) {
            if (s[p].v >= v)
                p = s[p].l;
            else {
                chkmax(ret, s[p].v);
                p = s[p].r;
            }
        }
        return ret;
    }

    int nxt(int v)
    {
        int p = root;
        int ret = 2e8;
        while (p) {
            if (s[p].v <= v)
                p = s[p].r;
            else {
                chkmin(ret, s[p].v);
                p = s[p].l;
            }
        }
        return ret;
    }

    int rank(int v)
    {
        int p = root;
        int ret = 0;
        while (p) {
            if (s[p].v <= v)
                ret += s[s[p].l].size + s[p].cnt, p = s[p].r;
            else
                p = s[p].l;
        }
        return ret;
    }

    void print(int x)
    {
        if (!x) return;
        if (s[x].l) print(s[x].l);
        for (int i = 1; i <= s[x].cnt; ++ i) write(s[x].v, ' ');
        if (s[x].r) print(s[x].r);
    }

} t[maxn << 2];
 
int n;
int m;
int a[maxn];

#define LS (x << 1)
#define RS (x << 1 | 1)

void build(int x, int l, int r)
{
    for (register int i = l; i <= r; ++ i)
        t[x].Insert(a[i]);

    if (l == r)
        return;

    int mid = (l + r) >> 1;

    build(LS, l, mid);
    build(RS, mid + 1, r);
}

inline int query_count(int x, int l, int r, int p, int q, int v)
{
    if (p <= l && r <= q)
        return t[x].rank(v);

    int mid = (l + r) >> 1;

    int ret = 0;

    if (p <= mid)
        ret += query_count(LS, l, mid, p, q, v);
    if (q > mid)
        ret += query_count(RS, mid + 1, r, p, q, v);

    return ret;
}

int query_index(int l, int r, int k)
{
    int L = 0, R = 1e8, mid;
    while (L <= R) {
        if (query_count(1, 1, n, l, r, mid = ((L + R) >> 1)) < k)
            L = mid + 1;
        else
            R = mid - 1;
    }
    return L;
}

inline void Delete(int x, int l, int r, int p, int v)
{
    t[x].Delete(t[x].root, v);

    if (l == r)
        return;

    int mid = (l + r) >> 1;

    if (p <= mid)
        Delete(LS, l, mid, p, v);
    else
        Delete(RS, mid + 1, r, p, v);
}

inline void Insert(int x, int l, int r, const int p, const int v)
{
    t[x].Insert(v);

    if (l == r)
        return;

    int mid = (l + r) >> 1;

    if (p <= mid)
        Insert(LS, l, mid, p, v);
    else
        Insert(RS, mid + 1, r, p, v);
}

inline int query_pre(int x, int l, int r, int p, int q, const int v)
{
    if (p <= l && r <= q)
        return t[x].pre(v);

    int mid = (l + r) >> 1;

    int ret = -1;

    if (p <= mid)
        chkmax(ret, query_pre(LS, l, mid, p, q, v));
    if (q > mid)
        chkmax(ret, query_pre(RS, mid + 1, r, p, q, v));

    return ret;
}

inline int query_nxt(int x, int l, int r, int p, int q, const int v)
{
    if (p <= l && r <= q)
        return t[x].nxt(v);

    int mid = (l + r) >> 1;

    int ret = 1e8 + 1;

    if (p <= mid)
        chkmin(ret, query_nxt(LS, l, mid, p, q, v));
    if (q > mid)
        chkmin(ret, query_nxt(RS, mid + 1, r, p, q, v));

    return ret;
}

#undef LS
#undef RS

void exec()
{
    read(n);
    read(m);

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

    build(1, 1, n);

    for (register int i = 1; i <= m; ++ i) {

        int opt, l, r, k;
        read(opt);

        if (opt != 3)
            read(l), read(r), read(k);
        else
            read(l), read(k);

        if (opt == 1)
            write(query_count(1, 1, n, l, r, k - 1) + 1);
        else if (opt == 2)
            write(query_index(l, r, k));
        else if (opt == 3)
            Delete(1, 1, n, l, a[l]), a[l] = k, Insert(1, 1, n, l, k);
        else if (opt == 4)
            write(query_pre(1, 1, n, l, r, k));
        else if (opt == 5)
            write(query_nxt(1, 1, n, l, r, k));
    }
}

/*{{{*/
int main() 
{
    if (fopen(iput.c_str(), "r") != NULL) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }

    exec();

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/

 

BZOJ2732: [HNOI2012]射箭
240 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航