BZOJ3196 Tyvj 1730 二逼平衡树 线段树套平衡树

yts1999 posted @ 2015年7月29日 08:50 in 树套树 with tags bzoj 树套树 splay 线段树 , 609 阅读

太神了。。。又调了5个小时。。。

/**************************************************************
    Problem: 3196
    User: yts1999
    Language: C++
    Result: Accepted
    Time:9436 ms
    Memory:83664 kb
****************************************************************/
 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;
 
const int oo = 1e8;
 
struct Treenode {
    int l,r,root;
};
 
int ch[1110000][2],fa[1110000],sz[1110000],key[1110000];
int a[1110000],b[1110000];
Treenode t[4440000];
stack<int> s;
int tot;
int op,x,sum,pre,suc,pl;
 
int dir(int x) {
    return x == ch[fa[x]][1];
}
 
int SIZE(int x) {
    if (x != 0)
        return sz[x];
    else
        return 0;
}
 
void update(int x) {
    sz[x] = SIZE(ch[x][0]) + SIZE(ch[x][1]) + 1;
}
 
void rotate(int K,int x) {
    int y = fa[x],b = dir(x);
    int z = fa[y],a = ch[x][! b];
    if (z == 0)
        t[K].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 K,int x,int i) {
    for (; fa[x] != i;) {
        int y = fa[x];
        int z = fa[y];
        if (z == i)
            rotate(K,x);
        else {
            int b = dir(x),c = dir(y);
            if (b ^ c) {
                rotate(K,x);
                rotate(K,x);
            }
            else {
                rotate(K,y);
                rotate(K,x);
            }
        }
    }
}
  
int find_min(int x) {
    for (; ch[x][0] != 0; x = ch[x][0]);
    return x;
}
 
int find_max(int x) {
    for (; ch[x][1] != 0; x = ch[x][1]);
    return x;
}
 
int find(int i,int x) {
    for (; i; i = ch[i][key[i] < x])
        if (key[i] == x)
            return i;
}
 
int find_pred(int i,int x) {
    if (i == 0)
        return 0;
    if (key[i] < x) {
        int y = find_pred(ch[i][1],x);
        if (y != 0)
            return y;
        else
            return i;
    }
    else
        return find_pred(ch[i][0],x);
}
 
int find_succ(int i,int x) {
    if (i == 0)
        return 0;
    if (key[i] > x) {
        int y = find_succ(ch[i][0],x);
        if (y != 0)
            return y;
        else
            return i;
    } 
    else
        return find_succ(ch[i][1],x);
}
 
void newnode(int f,int d,int k) {
    int x;
    if (s.empty())
        x = ++tot;
    else {
        x = s.top();
        s.pop();
    }
    fa[x] = f;
    ch[f][d] = x; 
    sz[x] = 1;
    key[x] = k;
    ch[x][0] = ch[x][1] = 0;
}
 
void build_splay(int f,int d,int l,int r) {
    int mid = (l + r) / 2;
    newnode(f,d,a[mid]);
    if (l < mid)
        build_splay(ch[f][d],0,l,mid - 1);
    if (r > mid)
        build_splay(ch[f][d],1,mid + 1,r);
    update(ch[f][d]);
}
 
void insert(int K,int x) {
    int i = t[K].root;
    for (; ch[i][key[i] < x]; i = ch[i][key[i] < x]);
    newnode(i,key[i] < x,x);
    splay(K,ch[i][key[i] < x],0);
}
 
void del(int K,int x) {
    int z = find(t[K].root,x);
    splay(K,z,0);
    int w = find_min(ch[z][1]);
    z = find_max(ch[z][0]);
    splay(K,z,0);
    splay(K,w,z);
    s.push(ch[w][0]);
    ch[w][0] = 0;
    update(w);
    update(z);
}
 
void build(int k,int l,int r) {
    t[k].l = l;
    t[k].r = r;
    if (l == r) {
        int x;
        if (s.empty())
            x = ++tot;
        else {
            x = s.top();
            s.pop();
        }
        fa[x] = 0;
        sz[x] = 1;
        key[x] = -oo;
        ch[x][0] = ch[x][1] = 0;
        t[k].root = x;
        newnode(x,1,oo);
        sz[x] = 2;
        build_splay(ch[x][1],0,l,r);
        update(ch[x][1]);
        update(x);
        return;
    }
    int mid = (l + r) / 2;
    build(k * 2,l,mid);
    build(k * 2 + 1,mid + 1,r);
    sort(a + l,a + r + 1);
    int x;
    if (s.empty())
        x = ++tot;
    else {
        x = s.top();
        s.pop();
    }
    fa[x] = 0;
    sz[x] = 1;
    key[x] = -oo;
    ch[x][0] = ch[x][1] = 0;
    t[k].root = x;
    newnode(x,1,oo); 
    sz[x] = 2;
    build_splay(ch[x][1],0,l,r);
    update(ch[x][1]);
    update(x);
}
 
void query(int k,int l,int r) {
    if (t[k].l == l && t[k].r == r) {
        if (op == 1) {
            insert(k,x);
            sum += sz[ch[t[k].root][0]] - 1;
            del(k,x);
        }
        if (op == 3) {
            del(k,b[pl]);
            insert(k,x);
        }
        if (op == 4)
            pre = max(pre,key[find_pred(t[k].root,x)]);
        if (op == 5)
            suc = min(suc,key[find_succ(t[k].root,x)]);
        return;
    }
    int mid = (t[k].l + t[k].r) / 2;
    if (l <= mid)
        query(k * 2,l,min(r,mid));
    if (r >= mid + 1)
        query(k * 2 + 1,max(mid + 1,l),r);
    if (op == 3) {
        del(k,b[pl]);
        insert(k,x);
    }
}
 
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i++) {
        scanf("%d",&a[i]);
        b[i] = a[i];
    }
    build(1,1,n);
    for (int i = 0; i < m; i++) {
        scanf("%d",&op);
        if (op == 1) {
            int l,r;
            scanf("%d%d%d",&l,&r,&x);
            sum = 0;
            query(1,l,r);
            printf("%d\n",sum + 1);
        }
        if (op == 2) {
            int ll,rr,k;
            scanf("%d%d%d",&ll,&rr,&k);
            op = 1;
            int ans;
            for (int l = 0,r = oo; l <= r;) {
                int mid = (l + r) / 2;
                sum = 0;
                x = mid; 
                query(1,ll,rr);
                if (sum + 1 <= k) {
                    ans = mid;
                    l = mid + 1;
                }
                else
                    r = mid - 1;
            }
            printf("%d\n",ans);
        }
        if (op == 3) {
            scanf("%d%d",&pl,&x);
            query(1,pl,pl);
            b[pl] = x;
        }
        if (op == 4) {
            int l,r;
            scanf("%d%d%d",&l,&r,&x);
            pre = -oo;
            query(1,l,r);
            printf("%d\n",pre);
        }
        if (op == 5) {
            int l,r;
            scanf("%d%d%d",&l,&r,&x);
            suc = oo;
            query(1,l,r);
            printf("%d\n",suc);
        }
    }
    return 0;
}

登录 *


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