说不定会再开一个坑呢(躺
备份一下代码

uva11922 190ms
非旋treap 笛卡尔树构造
用数组t了 动态指针反而能a

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <ctime>
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 = 1e5 + 1000, INF = 0x3f3f3f3f;
struct Node
{
    Node *l, *r;
    int key, val, size;
    bool rev;
    Node(int c, int d) : key(c), val(d){l = r = NULL; size = 1; rev = false;}
} *root;
#define lc(o) ((o) -> l)
#define rc(o) ((o) -> r)
#define k(o) ((o) -> key)
#define v(o) ((o) -> val)
#define s(o) ((o) ? (o) -> size : 0)
#define r(o) ((o) -> rev)
inline void maintain(Node*&o){o -> size = s(lc(o)) + s(rc(o)) + 1;}
Node *stack[maxn];
inline void build(int n)
{
    int top = 0;
    stack[top++] = new Node(-INF, -INF);
    for(int i = 1; i <= n; i++)
    {
        Node *newnode = new Node(i, rand());
        int t = top - 1;
        while(v(stack[t]) > v(newnode)) maintain(stack[t--]);
        if(t != top - 1) lc(newnode) = stack[t + 1];
        rc(stack[t]) = newnode;
        top = t + 1;
        stack[top++] = newnode;
    }
    while(top) maintain(stack[--top]);
    root = rc(stack[top]);
}
inline void pushdown(Node *o)
{
    if(!r(o)) return;
    if(lc(o)) r(lc(o)) ^= 1;
    if(rc(o)) r(rc(o)) ^= 1;
    r(o) ^= 1;
    swap(lc(o), rc(o));
}
void split(Node *o, int k, Node* &L, Node* &R)
{
    if(!o) return;
    pushdown(o);
    if(!k)
    {
        R = o;
        return; 
    }
    else if(s(lc(o)) >= k)
    {
        R = o; Node *tmp = lc(o); lc(R) = 0;
        split(tmp, k, L, lc(R));
        maintain(R);
    }
    else
    {
        L = o; Node *tmp = rc(o); rc(L) = 0;
        split(tmp, k - s(lc(o)) - 1, rc(L), R);
        maintain(L); 
    }
}
Node* merge(Node *L, Node *R)
{
    if(!L) return R;
    if(!R) return L;
    pushdown(L); pushdown(R);
    if(v(L) < v(R))
    {
        rc(L) = merge(rc(L), R);
        maintain(L);
        return L;
    }
    else
    {
        lc(R) = merge(L, lc(R));
        maintain(R);
        return R;
    }
}
void go(Node *o)
{
    pushdown(o);
    if(lc(o)) go(lc(o));
    printf("%d\n", k(o));
    if(rc(o)) go(rc(o));
}
int main()
{
    srand(time(NULL));
    int n, m; read(n, m);
    build(n);
    while(m--)
    {
        int l, r; read(l, r);
        Node *r1 = NULL, *r2 = NULL, *r3 = NULL, *r4 = NULL;
        split(root, l - 1, r1, r2);
        split(r2, r - l + 1, r3, r4);
        r(r3) = true;
        r2 = merge(r4, r3);
        root = merge(r1, r2);
    }
    go(root);
    return 0;
}

uva 12538 180ms
可持久化
哈哈哈终于让我写了出来

#include <cstdio>
#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 = 1e6, INF = 0x3f3f3f3f;
struct Node{Node *ch[2]; char k; int v, size; Node(char c,int d):k(c),v(d){ch[0]=ch[1]=NULL;size=1;}} *root[maxn];
#define lc(o) ((o) -> ch[0])
#define rc(o) ((o) -> ch[1])
#define k(o) ((o) -> k)
#define v(o) ((o) -> v)
#define s(o) ((o) ? (o) -> size : 0)
inline void maintain(Node*&o){if(o) o -> size = s(lc(o)) + s(rc(o)) + 1;}
Node* merge(Node *a, Node *b)
{
    if(!a) return b;
    if(!b) return a;
    if(v(a) < v(b))
    {
        Node *na = new Node(0, 0); *na = *a;
        rc(na) = merge(rc(na), b);
        maintain(na);
        return na;
    }
    Node *nb = new Node(0, 0); *nb = *b;
    lc(nb) = merge(a, lc(nb));
    maintain(nb);
    return nb;
}
void split(Node *o, int k, Node*&a, Node*&b)
{
    if(!o) return;
    if(!k)
    {
        b = new Node(0, 0); 
        *b = *o; 
        return;
    }
    if(s(lc(o)) >= k)
    {
        b = new Node(0, 0); *b = *o; lc(b) = NULL;
        split(lc(o), k, a, lc(b));
        maintain(b);
    }
    else
    {
        a = new Node(0, 0); *a = *o; rc(a) = NULL;
        split(rc(o), k - s(lc(o)) - 1, rc(a), b);
        maintain(a);
    }
}
Node *stack[maxn];
Node* build(char *s)
{
    int top = 0;
    stack[top++] = new Node(0, -INF);
    int len = strlen(s);
    for(int i = 0; i < len; i++)
    {
        int t = top - 1;
        Node *newnode = new Node(s[i], rand());
        while(v(stack[t]) > v(newnode)) maintain(stack[t--]);
        if(t != top - 1) lc(newnode) = stack[t + 1];
        rc(stack[t]) = newnode;
        top = t + 1;
        stack[top++] = newnode;
    }
    while(top) maintain(stack[--top]);
    return rc(stack[top]);
}
int d = 0;
void output(Node *o)
{
    if(!o) return;
    if(lc(o)) output(lc(o));
    putchar(k(o));
    if(k(o) == 'c') d++;
    if(rc(o)) output(rc(o));
}
char s[maxn];
int main()
{
    int n, t, p, c, v; read(n);
    Node *x, *y, *z, *w;
    int cnt = 0;
    root[cnt++] = NULL;
    while(n--)
    {
        read(t);
        if(t == 1)
        {
            read(p); p -= d; scanf("%s", &s);
            x = NULL, y = NULL;
            split(root[cnt - 1], p, x, y);
            root[cnt++] = merge(merge(x, build(s)), y);
        }
        else if(t == 2)
        {
            read(p, c); p -= d, c -= d;
            x = NULL, y = NULL, z = NULL, w = NULL;
            split(root[cnt - 1], p - 1, x, y);
            split(y, c, z, w);
            root[cnt++] = merge(x, w);
        }
        else
        {
            read(v, p, c); v -= d, p -= d, c -= d;
            x = NULL, y = NULL, z = NULL, w = NULL;
            split(root[v], p - 1, x, y);
            split(y, c, z, w);
            output(z); puts("");
        }
    }
    return 0;
}

标签: none

添加新评论