BZOJ1895 Pku3580 supermemo Splay

yts1999 posted @ 2015年7月26日 17:20 in Splay with tags bzoj splay , 666 阅读

裸Splay不解释

详情见代码

/**************************************************************
    Problem: 1895
    User: yts1999
    Language: C++
    Result: Accepted
    Time:8604 ms
    Memory:7720 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
  
const int oo = 0x7fffffff;
  
int ch[200010][2];
int fa[200010],key[200010],sz[200010],tag[200010],mn[200010],a[200010];
bool rev[200010];
int root,tot;
int ans = 0;
  
int dir(int x) {
    return x == ch[fa[x]][1];
} 
  
int SIZE(int x) {
    if (x != 0)
        return sz[x];
    else
        return 0;
}
 
int MIN(int x) {
    if (x != 0)
        return mn[x];
    else
        return oo;
}
 
void update(int x) {
    sz[x] = SIZE(ch[x][0]) + SIZE(ch[x][1]) + 1;
    mn[x] = min(MIN(ch[x][0]),min(MIN(ch[x][1]),key[x]));
}
 
void updateroot(int x) {
    for (; x != 0; x = fa[x])
        update(x);
}
 
void mutate(int i,int x) {
    tag[i] += x;
    key[i] += x;
    mn[i] += x;
}
 
void release(int x) {
    if (rev[x]) {
        swap(ch[x][0],ch[x][1]);
        if (ch[x][0] != 0)
            rev[ch[x][0]] = ! rev[ch[x][0]];
        if (ch[x][1] != 0)
            rev[ch[x][1]] = ! rev[ch[x][1]];
        rev[x] = 0;
    }
    if (tag[x] != 0) {
        if (ch[x][0] != 0)
            mutate(ch[x][0],tag[x]);
        if (ch[x][1] != 0)
            mutate(ch[x][1],tag[x]);
        tag[x] = 0;
    }
}
 
void rotate(int x) {
    int y = fa[x],b = dir(x);
    int z = fa[y],a = ch[x][!b];
    if (z == 0)
        root = x;
    else
        ch[z][dir(y)] = x;
    fa[x] = z;
    ch[x][!b] = y;
    fa[y] = x;
    ch[y][b] = a;
    if (a != 0)
        fa[a] = y;
    update(y);
    update(x);
}
  
void splay(int x,int i) {
    for (; fa[x] != i;) {
        int y = fa[x];
        int z = fa[y];
        if (z == i) {
            release(y);
            release(x);
            rotate(x);
        }
        else {
            release(z);
            release(y);
            release(x);
            int b = dir(x), c = dir(y);
            if (b ^ c) {
                rotate(x);
                rotate(x);
            }
            else {
                rotate(y);
                rotate(x);
            }
        }
    }
}
  
int find(int i,int x) {
    release(i);
    if (SIZE(ch[i][0]) + 1 == x)
        return i;
    else
        if (SIZE(ch[i][0]) + 1 < x)
            return find(ch[i][1],x - SIZE(ch[i][0]) - 1);
        else
            return find(ch[i][0],x);
}
 
void build(int f,int d,int l,int r) {
    fa[++tot] = f;
    ch[f][d] = tot;
    sz[tot] = 1;
    tag[tot] = 0;
    rev[tot] = 0;
    int mid = (l + r) / 2;
    key[tot] = a[mid];
    int x = tot;
    if (l < mid)
        build(x,0,l,mid - 1);
    if (r > mid)
        build(x,1,mid + 1,r);
    update(x);
}
 
void insert(int f,int d,int k) {
    fa[++tot] = f;
    ch[f][d] = tot;
    sz[tot] = 1;
    tag[tot] = 0;
    rev[tot] = 0;
    mn[tot] = key[tot] = k;
}
 
int main() {
    int n;
    scanf("%d",&n);
    root = 1;
    tot = 2; 
    ch[1][0] = 0;
    ch[1][1] = 2;
    fa[1] = 0;
    sz[1] = 2;
    tag[1] = 0;
    key[1] = oo;
    mn[1] = oo;
    rev[1] = 0;
    ch[2][0] = ch[2][1] = 0;
    fa[2] = 1;
    sz[2] = 1;
    tag[2] = 0;
    key[2] = oo;
    mn[2] = oo;
    rev[2] = 0;
    for (int i = 1; i <= n; i++)
        scanf("%d",&a[i]);
    build(2,0,1,n);
    updateroot(3);
    int m;
    scanf("%d",&m);
    for (; m--;) {
        char s[10];
        scanf("%s",s);
        if (s[0] == 'M') {
            int x,y;
            scanf("%d%d",&x,&y);
            int z = find(root,x);
            splay(z,0);
            int w = find(root,y + 2);
            splay(w,z);
            printf("%d\n",mn[ch[w][0]]);
        }
        if (s[0] == 'A') {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            int z = find(root,x);
            splay(z,0);
            int w = find(root,y + 2);
            splay(w,z);
            int u = ch[w][0];
            mutate(u,d);
            updateroot(w);
        }
        if (s[0] == 'I') {
            int x,d;
            scanf("%d%d",&x,&d);
            int z = find(root,x + 1);
            splay(z,0);
            int w = find(root,x + 2);
            splay(w,z);
            insert(w,0,d);
            updateroot(w);
        }
        if (s[0] == 'D') {
            int x;
            scanf("%d",&x);
            int z = find(root,x);
            splay(z,0);
            int w = find(root,x + 2);
            splay(w,z);
            ch[w][0] = 0;
            updateroot(w);
        }
        if (s[0] == 'R' && s[3] == 'E') {
            int x,y;
            scanf("%d%d",&x,&y);
            int z = find(root,x);
            splay(z,0);
            int w = find(root,y + 2);
            splay(w,z);
            int u = ch[w][0];
            rev[u] = ! rev[u];
            release(u);
            updateroot(w);
        }
        if (s[0] == 'R' && s[3] == 'O') {
            int x,y,d;
            scanf("%d%d%d",&x,&y,&d);
            d %= y - x + 1;
            if (d == 0)
                continue;
            int z = find(root,y - d + 1);
            splay(z,0);
            int w = find(root,y + 2);
            splay(w,z);
            int u = ch[w][0];
            ch[w][0] = 0;
            updateroot(w);
            z = find(root,x);
            splay(z,0);
            w = find(root,x + 1);
            splay(w,z);
            fa[u] = w;
            ch[w][0] = u;
            updateroot(w);
        }
    }
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter