HDU

题意:单点修改,区间最值。

裸线段树。
当然像我一样尝试使用黑科技,用split/merge的treap做也可以。
很多地方没有理解清楚。细节也实现得像shi一样。
多亏了@plm大神指导。感谢!!

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T, class U>
inline void read(T& x, U& y){read(x), read(y);}
template<class T, class U, class V>
inline void read(T& x, U& y, V& z){read(x), read(y), read(z);}

const int maxn = 2e5 + 100;

struct Node
{
    int num, v;
    int tag; 
    int r;
    Node* ch[2];
    int size;
    Node(int a = 0, int b = 0, int c = 0, int d = 0) : num(a), v(b), r(c), size(d) {ch[0] = ch[1] = NULL; tag = v;}
} pool[maxn], *root;
int cnt = 0;

#define lc(x) (x -> ch[0])
#define rc(x) (x -> ch[1])
#define size(x) (x ? x -> size : 0)
#define tag(x) (x ? x -> tag : 0)

inline void maintain(Node* o)
{
    if(o)
    {
        o -> size = size(lc(o)) + size(rc(o)) + 1; 
        o -> tag = max(max(tag(lc(o)), tag(rc(o))), o -> v);
    }
}

Node* merge(Node* x, Node* y)//x << y
{
    if(!x)
        return y;
    if(!y)
        return x;
    if((x -> r)  >  (y -> r))
    {
        rc(x) = merge(rc(x), y);
        maintain(x);
        return x;
    }
    lc(y) = merge(x, lc(y));
    maintain(y);
    return y;
}

void split(Node* o, Node* &x, Node* &y, int k)
{
    if(!o)
        return;
    if(!k)
    {
        x = NULL, y = o;
        return;
    }
    int d = size(lc(o));
    if(d + 1 == k)
    {
        y = rc(o);
        rc(o) = NULL;
        maintain(o);
        x = o;
    }
    else if(d + 1 > k)
    {
        split(lc(o), x, y, k);//split(lc[o], x, lc[y], k)
        lc(o) = y;
        maintain(o);
        y = o;
    }
    else
    {
        split(rc(o), x, y, k - d - 1);
        rc(o) = x;
        maintain(o);
        x = o;
    }
}

void insert(Node* &o, int k, int x)
{
    Node* newnode = &pool[++cnt];
    *newnode = Node(k, x, rand(), 1);
    o = merge(o, newnode);
    maintain(o);
}

void update(Node* o, int k, int x)
{
    Node *a = NULL, *b = NULL, *node = NULL, *c = NULL;
    split(o, a, b, k - 1);
    split(b, node, c, 1);
    node -> v = x;
    node -> tag = x;
    a = merge(a, node);
    a = merge(a, c);
}

int query(Node* o, int x, int y)
{
    Node *a = NULL, *b = NULL, *c = NULL, *d = NULL;
    split(o, a, b, y);
    split(a, c, d, x - 1);
    int ret = d -> tag;
    o = merge(c, d);
    o = merge(o, b);
    return ret;
}

int main()
{
    srand(233);
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        memset(pool, 0, sizeof pool);
        cnt = 0;
        root = NULL;
        for(int i = 1; i <= n; i++)
        {
            int x;
            read(x);
            insert(root, i, x);
        }
        while(m--)
        {
            char code[2]; int a, b;
            scanf("%s", &code); read(a, b);
            if(code[0] == 'U')
            {
                update(root, a, b);
            }
            else
                    printf("%d\n", query(root, a, b));
        }
    }
    return 0;
}

标签: treap

添加新评论