仅仅只是贴个模板而已。。。

bzoj3224-treap-插入删除前驱后继

#include <cstdio>
#include <algorithm>
const int N = 1000000 + 9;
int l[N],r[N],sz[N],rnd[N],p[N],n,key[N],cnt,rt,last,flag,*P[N];
void update(const int x)
{
    if (!x) return;
    sz[x] = sz[l[x]] + sz[r[x]] + 1;
}
void rig_rotate(int &k)
{
    const int x = k,y = l[x];
    p[y] = p[x];
    k = y;
    p[r[y]] = x;
    l[x] = r[y];
    p[x] = y;
    r[y] = x;
    sz[y] = sz[x];
    update(x);
}
void lef_rotate(int &k)
{
    const int x = k,y = r[x];
    p[y] = p[x];
    k = y;
    p[l[y]] = x;
    r[x] = l[y];
    p[x] = y;
    l[y] = x;
    sz[y] = sz[x];
    update(x);
}
int findp(const int x)
{
    int ans = -0x3f3f3f3f;
    for (int idx = rt; idx; )
        if (key[idx] < x) {
            ans = std::max(ans,key[idx]);
            idx = r[idx];
        }else idx = l[idx];
    return ans;
}
int finds(const int x)
{
    int ans = 0x3f3f3f3f;
    for (int idx = rt; idx; )
        if (key[idx] > x) {
            ans = std::min(ans,key[idx]);
            idx = l[idx];
        }else idx = r[idx];
    return ans;
}
int rank(int x)
{
    for (int idx = rt; idx; )
        if (x > sz[l[idx]]) {
            x -= sz[l[idx]] + 1;
            if (x == 0) return key[idx];
            idx = r[idx];
        }else idx = l[idx];
    return 10086;
}
int rankof(const int x)
{
    int ans = 0;
    for (int idx = rt; idx; )
        if (key[idx] < x) {ans += sz[l[idx]] + 1;idx = r[idx];}
        else idx = l[idx];
    return ans + 1;
}
void Ins(const int x)
{
    int k = 0,fa = 0;
    P[++k] = &rt;
    for (; *P[k] && (fa = *P[k]); ++k)
        if (key[*P[k]] < x) P[k + 1] = &r[*P[k]];
        else P[k + 1] = &l[*P[k]];
    *P[k] = ++cnt;
    rnd[cnt] = rand();
    p[cnt] = fa;
    key[cnt] = x;
    sz[cnt] = 1;
    for (; fa; fa = p[fa]) update(fa);
    for (; k && rnd[*P[k]] < rnd[cnt]; --k)
        if (l[*P[k]] == cnt) rig_rotate(*P[k]);
        else lef_rotate(*P[k]);
}
void Del(const int x)
{
    int *P = &rt;
    while (key[*P] != x)
        if (key[*P] < x) P = &r[*P];
        else P = &l[*P];
    while (l[*P] && r[*P])
        if (rnd[l[*P]] > rnd[r[*P]]) {rig_rotate(*P); P = &r[*P];}
        else {lef_rotate(*P); P = &l[*P];}
    p[l[*P] + r[*P]] = p[*P];
    *P = l[*P] + r[*P];
    for (int idx = p[*P]; idx; idx = p[idx]) update(idx);
}
int main()
{
    #ifndef ONLINE_JUDGE
 freopen("3224.in","r",stdin);
    freopen("3224.out","w",stdout);
    #endif
 scanf("%d",&n);
    for (int opt,x; n--; ) {
        scanf("%d%d",&opt,&x);
        if (opt == 1) Ins(x);
        else if (opt == 2) Del(x);
        else if (opt == 3) printf("%d\n",rankof(x));
        else if (opt == 4) printf("%d\n",rank(x));
        else if (opt == 5) printf("%d\n",findp(x));
        else printf("%d\n",finds(x));
    }
}

lct(splay) bzoj3091

#include <cstdio>
#include <algorithm>
const int N = 50000 + 9;
long long sum[N],lsum[N],rsum[N],a[N],ans[N],add[N];
int n,m,l[N],r[N],p[N],sz[N],ec,son[N],nxt[N * 2],lnk[N * 2];
bool rev[N];
inline void release(const int x)
{
    if (rev[x]) {
        rev[l[x]] ^= 1; rev[r[x]] ^= 1;
        rev[x] = 0;
        std::swap(l[x],r[x]);
        std::swap(lsum[x],rsum[x]);
    }
    if (add[x]) {
        add[l[x]] += add[x]; add[r[x]] += add[x];
        ans[x] += add[x] * (1ll * sz[x] * (sz[x] + 1) * (sz[x] + 2) / 6);
        lsum[x] += add[x] * (1ll * sz[x] * (sz[x] + 1) / 2);
        rsum[x] += add[x] * (1ll * sz[x] * (sz[x] + 1) / 2);
        a[x] += add[x];
        sum[x] += add[x] * sz[x];
        add[x] = 0;
    }
}
inline void update(const int x)
{
    release(x); release(l[x]); release(r[x]);
    sz[x] = sz[l[x]] + sz[r[x]] + 1;
    ans[x] = ans[l[x]] + lsum[l[x]] * (sz[r[x]] + 1) + ans[r[x]] + rsum[r[x]] * (sz[l[x]] + 1) + (sz[l[x]] + 1) * (sz[r[x]] + 1) * a[x];
    lsum[x] = lsum[l[x]] + lsum[r[x]] + (sz[l[x]] + 1) * sum[r[x]] + a[x] * (sz[l[x]] + 1);
    rsum[x] = rsum[r[x]] + rsum[l[x]] + (sz[r[x]] + 1) * sum[l[x]] + a[x] * (sz[r[x]] + 1);
    sum[x] = sum[l[x]] + sum[r[x]] + a[x];
}
inline void rig_rotate(int x)
{
    int y = l[x];
    p[y] = p[x];
    if (l[p[y]] == x) l[p[y]] = y;
    else if (r[p[y]] == x) r[p[y]] = y;
    p[r[y]] = x;
    l[x] = r[y];
    p[x] = y;
    r[y] = x;
    update(x);
    if (l[0] || r[0])
        puts("Orz heibangbang");
}
inline void lef_rotate(int x)
{
    int y = r[x];
    p[y] = p[x];
    if (l[p[y]] == x) l[p[y]] = y;
    else if (r[p[y]] == x) r[p[y]] = y;
    p[l[y]] = x;
    r[x] = l[y];
    p[x] = y;
    l[y] = x;
    update(x);
    if (l[0] || r[0])
        puts("Orz heibangbang");
}
inline bool isrt(int x){return !p[x] || (l[p[x]] != x && r[p[x]] != x);}
void splay(int x)
{
    release(x);
    while (!isrt(x)) {
        int y = p[x],z = p[y];
        if (!isrt(y)) release(z);
        release(y); release(x);
        if (!isrt(y) && l[z] == y && l[y] == x) rig_rotate(z),rig_rotate(y);
        else if (!isrt(y) && r[z] == y && r[y] == x) lef_rotate(z),lef_rotate(y);
        else if (l[y] == x) rig_rotate(y);
        else lef_rotate(y);
    }
    update(x);
}
void access(int rt)
{
    for (int y = rt,x = 0; y; y = p[y]) {
        splay(y);
        r[y] = x;
        update(x = y);
    }
    splay(rt);
}
int find_rt(int x){access(x);for (release(x); l[x]; ) release(x = l[x]);return x;}
inline void make_rt(const int x)
{
    access(x);
    rev[x] ^= 1;
}
inline void cut(const int x,const int y)
{
    make_rt(x);
    access(y);
    if (p[x] != y || sz[y] != 2) return;
    p[x] = 0;
    l[y] = 0;
    update(y);
}
inline void link(const int x,const int y)
{
    if (find_rt(x) == find_rt(y)) return;
    make_rt(x);
    p[x] = y;
}
inline void addedge(const int x,const int y)
{
    nxt[++ec] = son[x];
    son[x] = ec;
    lnk[ec] = y;
}
void dfs(const int x)
{
    for (int i = son[x]; i; i = nxt[i])
        if (lnk[i] == p[x]) continue;
        else {p[lnk[i]] = x; dfs(lnk[i]);}
}
long long gcd(long long a,long long b){return b ? gcd(b,a % b) : a;}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("3091.in","r",stdin);
    freopen("3091.out","w",stdout);
    #endif
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld",a + i);
        ans[i] = sum[i] = rsum[i] = lsum[i] = a[i];
        sz[i] = 1;
    }
    for (int x,y,i = 1; i < n; ++i) {
        scanf("%d%d",&x,&y);
        addedge(x,y);
        addedge(y,x);
    }
    dfs(1);
    for (int x,y,z,opt; m--;) {
        scanf("%d%d%d",&opt,&x,&y);
        if (opt == 1) cut(x,y);
        else if (opt == 2) link(x,y);
        else if (opt == 3) {
            scanf("%d",&z);
            make_rt(x);
            if (find_rt(y) != x) continue;
            access(y);
            add[y] += z;
        }else {
            make_rt(x);
            if (find_rt(y) != x) {puts("-1");continue;}
            access(y);
            long long tx = ans[y],ty = 1ll * sz[y] * (sz[y] + 1) / 2,g = gcd(tx,ty);
            printf("%lld/%lld\n",tx / g,ty / g);
        }
    }
}

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project