BZOJ 1895 & POJ 3580 supermemo [SPLAY]【数据结构】

前端之家收集整理的这篇文章主要介绍了BZOJ 1895 & POJ 3580 supermemo [SPLAY]【数据结构】前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

题目链接http://poj.org/problem?id=3580
——————————————————————————————————————————
SuperMemo
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 15846 Accepted: 4992
Case Time Limit: 2000MS
Description

Your friend,Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first,the host tells the participant a sequence of numbers,{A1,A2,… An}. Then the host performs a series of operations and queries on the sequence which consists:

ADD x y D: Add D to each number in sub-sequence {Ax … Ay}. For example,performing “ADD 2 4 1” on {1,2,3,4,5} results in {1,5,5}
REVERSE x y: reverse the sub-sequence {Ax … Ay}. For example,performing “REVERSE 2 4” on {1,5}
REVOLVE x y T: rotate sub-sequence {Ax … Ay} T times. For example,performing “REVOLVE 2 4 2” on {1,5}
INSERT x P: insert P after Ax. For example,performing “INSERT 2 4” on {1,5}
DELETE x: delete Ax. For example,performing “DELETE 2” on {1,5}
MIN x y: query the participant what is the minimum number in sub-sequence {Ax … Ay}. For example,the correct answer to “MIN 2 4” on {1,5} is 2
To make the show more interesting,the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains n (n ≤ 100000).

The following n lines describe the sequence.

Then follows M (M ≤ 100000),the numbers of operations and queries.

The following M lines describe the operations and queries.

Output

For each “MIN” query,output the correct answer.

Sample Input

5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
Sample Output

5

——————————————————————————————————————————

题意:
  给出一个数字序列,有6种操作:

    (1) ADD x y d: 第x个数到第y个数加d 。

    (2) REVERSE x y : 将区间[x,y]中的数翻转 。

    (3) REVOLVE x y t :将区间[x,y]旋转t次,如1 2 3 4 5 旋转2次后就变成4 5 1 2 3 。

    (4) INSERT x p :在第x个数后面插入p 。

    (5)DELETE x :删除第x个数 。

    (6) MIN x y : 查询区间[x,y]中的最小值 。


本来不想写来着 但想到 好多天没有更新博客了,加上这题还是挺好玩儿的,还是应该更新一波吧。

就是区间加,翻转,剪切,询问最值。点插入,删除。这几个操作

有翻转了 所以用SPLAY来维护一下

区间加 区间最小值就不说了 和普通的二叉搜索树一模一样.

点插入 删除

假如要插入的点在x
那么让x-1做为树根,x+1伸展到根节点下面,那么x+1的左儿子就是空出来的 加个值就好了
删除发过来一样的

区间操作

对于区间[l,r]
那么让l-1做为树根,r+1伸展到根节点下面,那么r+1的左儿子就是这个区间

但为了更好的处理[1,n]这个区间 加上个0和n+1这两个节点

翻转

同样在一个二叉树中 翻转也就是让每个节点的两个儿子交换一下顺序就好了,打个标记 就行了,

旋转

其实旋转说白了就是将这个区间分成两段然后交换一下子,

所以我们可以将后一个区间处理到一个子树上,然后放到@H_404_112@ l@H_404_112@−@H_404_112@1@H_404_112@,@H_404_112@l@H_404_112@@H_404_112@@H_404_112@@H_404_112@@H_404_112@@H_404_112@@H_404_112@@H_404_112@ @H_404_112@这两个节点之间,就好了,先减掉,然后在加上去就好了

注: 个人的SPLAY模板正在建设,这个的代码比较杂乱,见谅.

附本题代码
——————————————————————————————————————————

//#include <bits/stdc++.h>@H_404_112@
#include <stdio.h>

typedef long@H_404_112@ long@H_404_112@ int@H_404_112@ LL;

const@H_404_112@ int@H_404_112@ N = 200000@H_404_112@+7@H_404_112@;

inline int@H_404_112@ read(){
    int@H_404_112@ x=0@H_404_112@,f=1@H_404_112@;char@H_404_112@ ch=getchar();
    for@H_404_112@(;ch<'0'@H_404_112@||'9'@H_404_112@<ch;ch=getchar())   if@H_404_112@(ch=='-'@H_404_112@)f=-1@H_404_112@;
    for@H_404_112@(;'0'@H_404_112@<=ch&&ch<='9'@H_404_112@;ch=getchar()) x=(x<<3@H_404_112@)+(x<<1@H_404_112@)+ch-'0'@H_404_112@;
    return@H_404_112@ x*f;
}

/*******************************************************/@H_404_112@

/*************SPLAY-tree************/@H_404_112@

int@H_404_112@ n,m;

int@H_404_112@ ch[N][2@H_404_112@];  //ch[][0] lson ch[][1] rson@H_404_112@
int@H_404_112@ f[N];      //father@H_404_112@
int@H_404_112@ sz[N];     //size@H_404_112@
int@H_404_112@ val[N];    //value of node_i@H_404_112@
int@H_404_112@ lazy[N];   //lazy-tag@H_404_112@
int@H_404_112@ mi[N];     //min of son-tree : root of i@H_404_112@
int@H_404_112@ rev[N];    //tag of revear@H_404_112@
int@H_404_112@ root;      //root of splay-tree@H_404_112@
int@H_404_112@ tot;       //tot,total,is the number of node of tree@H_404_112@

void@H_404_112@ myswap(int@H_404_112@ &x,int@H_404_112@ &y){
    x^=y,y^=x,x^=y;
}
int@H_404_112@ min(int@H_404_112@ x,int@H_404_112@ y){
    return@H_404_112@ (x<y)?x:y;
}
void@H_404_112@ update_rev(int@H_404_112@ x){
    if@H_404_112@(!x) return@H_404_112@ ;
    myswap(ch[x][0@H_404_112@],ch[x][1@H_404_112@]);
    rev[x]^=1@H_404_112@;
}

void@H_404_112@ update_add(int@H_404_112@ x,int@H_404_112@ v){
    if@H_404_112@(x) lazy[x]+=v,val[x]+=v,mi[x]+=v;
}

void@H_404_112@ pushdown(int@H_404_112@ x){
    if@H_404_112@(!x) return@H_404_112@ ;
    if@H_404_112@(lazy[x]){
        update_add(ch[x][0@H_404_112@],lazy[x]);
        update_add(ch[x][1@H_404_112@],lazy[x]);
        lazy[x]=0@H_404_112@;
    }
    if@H_404_112@(rev[x]){
        update_rev(ch[x][0@H_404_112@]);
        update_rev(ch[x][1@H_404_112@]);
        rev[x]=0@H_404_112@;
    }
}

void@H_404_112@ pushup(int@H_404_112@ x){
    if@H_404_112@(!x)return@H_404_112@ ;
    sz[x]=1@H_404_112@,mi[x]=val[x];
    if@H_404_112@(ch[x][0@H_404_112@])sz[x]+=sz[ch[x][0@H_404_112@]],mi[x]=min(mi[x],mi[ch[x][0@H_404_112@]]);
    if@H_404_112@(ch[x][1@H_404_112@])sz[x]+=sz[ch[x][1@H_404_112@]],mi[ch[x][1@H_404_112@]]);
}

void@H_404_112@ rotate(int@H_404_112@ x,int@H_404_112@ k){   // k = 0 左旋, k = 1 右旋@H_404_112@
    int@H_404_112@ y=f[x];int@H_404_112@ z=f[y];
    pushdown(y),pushdown(x);
    ch[y][!k]=ch[x][k];if@H_404_112@(ch[x][k])f[ch[x][k]]=y;
    f[x]=z;if@H_404_112@(z)ch[z][ch[z][1@H_404_112@]==y]=x;
    f[y]=x;ch[x][k]=y;
    pushup(y),pushup(x);
}
/*** 这样的SPLAY 不好么? 相比分6种旋转的 zig-zag */@H_404_112@
void@H_404_112@ splay(int@H_404_112@ x,int@H_404_112@ goal){
    for@H_404_112@(int@H_404_112@ y=f[x];f[x]!=goal;y=f[x])
        rotate(x,(ch[y][0@H_404_112@]==x));
    if@H_404_112@(goal==0@H_404_112@) root=x;
}

void@H_404_112@ newnode(int@H_404_112@ rt,int@H_404_112@ v,int@H_404_112@ fa){
// printf("%d <---\n",rt);@H_404_112@
    f[rt]=fa;
    mi[rt]=val[rt]=v;sz[rt]=1@H_404_112@;
    ch[rt][0@H_404_112@]=ch[rt][1@H_404_112@]=rev[rt]=lazy[rt]=0@H_404_112@;
}
void@H_404_112@ delnode(int@H_404_112@ rt){
    f[rt]=mi[rt]=val[rt]=sz[rt]=0@H_404_112@;
    ch[rt][0@H_404_112@]=ch[rt][1@H_404_112@]=rev[rt]=lazy[rt]=0@H_404_112@;
}
void@H_404_112@ build(int@H_404_112@ &rt,int@H_404_112@ l,int@H_404_112@ r,int@H_404_112@ fa){
    if@H_404_112@(l>r) return@H_404_112@ ;
    int@H_404_112@ m = r+l >> 1@H_404_112@;
    rt=m; newnode(rt,val[rt],fa);
    build(ch[rt][0@H_404_112@],l,m-1@H_404_112@,rt);
    build(ch[rt][1@H_404_112@],m+1@H_404_112@,r,rt);
    pushup(rt);
}

void@H_404_112@ init(int@H_404_112@ n){
    root=0@H_404_112@;
    f[0@H_404_112@]=sz[0@H_404_112@]=ch[0@H_404_112@][0@H_404_112@]=ch[0@H_404_112@][1@H_404_112@]=rev[0@H_404_112@]=0@H_404_112@;
    build(root,1@H_404_112@,n,0@H_404_112@);
    pushup(root);
}

/***************************以下是DEBUG***************************/@H_404_112@

void@H_404_112@ Traversal(int@H_404_112@ rt){
    if@H_404_112@(!rt) return@H_404_112@;
    pushdown(ch[rt][0@H_404_112@]);Traversal(ch[rt][0@H_404_112@]);
    printf("%d f[]=%d sz[]=%d lson=%d rson=%d val[]=%d mi[]=%d \n"@H_404_112@,rt,f[rt],sz[rt],ch[rt][0@H_404_112@],ch[rt][1@H_404_112@],mi[rt]);
    pushdown(ch[rt][1@H_404_112@]);Traversal(ch[rt][1@H_404_112@]);
    pushup(rt);
}
void@H_404_112@ debug(){
    printf("ROOT = %d <---\n"@H_404_112@,root);
    pushdown(root);
    Traversal(root);
}

/**************************以下是前置操作**************************/@H_404_112@

//以x为根的子树 的最左节点@H_404_112@
int@H_404_112@ x_left(int@H_404_112@ x){
    for@H_404_112@(pushdown(x);ch[x][0@H_404_112@];pushdown(x)) x=ch[x][0@H_404_112@];
    return@H_404_112@ x;
}
//以x为根的子树 的最右节点@H_404_112@
int@H_404_112@ x_right(int@H_404_112@ x){
    for@H_404_112@(pushdown(x);ch[x][1@H_404_112@];pushdown(x)) x=ch[x][1@H_404_112@];
    return@H_404_112@ x;
}
//以x为根的子树 第k个数的位置@H_404_112@
int@H_404_112@ kth(int@H_404_112@ x,int@H_404_112@ k){
    pushdown(x);
    if@H_404_112@(sz[ch[x][0@H_404_112@]]+1@H_404_112@ == k) return@H_404_112@ x;
    else@H_404_112@ if@H_404_112@(sz[ch[x][0@H_404_112@]]>=k) return@H_404_112@ kth(ch[x][0@H_404_112@],k);
    else@H_404_112@ return@H_404_112@ kth(ch[x][1@H_404_112@],k-sz[ch[x][0@H_404_112@]]-1@H_404_112@);
}

/***************************以下是正经操作**************************/@H_404_112@
/*** 如果有区间为[1,n]情况不好处理, 所以我们可以 多添加一个head,一个tail 这样的话区间[1,n]就是tail的左儿子了,*/@H_404_112@
//区间交换@H_404_112@
void@H_404_112@ exchange(int@H_404_112@ l1,int@H_404_112@ r1,int@H_404_112@ l2,int@H_404_112@ r2){
    int@H_404_112@ x=kth(root,l2-1@H_404_112@),y=kth(root,r2+1@H_404_112@);
    splay(x,0@H_404_112@),splay(y,x);
    int@H_404_112@ tmp_right = ch[y][0@H_404_112@]; ch[y][0@H_404_112@]=0@H_404_112@;
    x=kth(root,l1-1@H_404_112@),l1);
    splay(x,x);
    ch[y][0@H_404_112@] = tmp_right;
    f[tmp_right]=y;
}

//区间翻转@H_404_112@
void@H_404_112@ reversal(int@H_404_112@ l,int@H_404_112@ r){
    int@H_404_112@ x=kth(root,l-1@H_404_112@),r+1@H_404_112@);
    splay(x,0@H_404_112@);splay(y,x);
    update_rev(ch[y][0@H_404_112@]);
}

//区间加@H_404_112@
void@H_404_112@ add(int@H_404_112@ l,int@H_404_112@ v){
    int@H_404_112@ x=kth(root,x);
    update_add(ch[y][0@H_404_112@],v);
}

//按照二叉排序树性质插入x@H_404_112@
void@H_404_112@ _insert(int@H_404_112@ x){
    /** 其实我们也可以 将插入后临街的两个节点 a x b 将a伸展到根 b伸展到 根下 那么b的左儿子一定没有,插进去就行了, */@H_404_112@
}

//在第k个数后插入值为x的节点@H_404_112@
void@H_404_112@ _insert(int@H_404_112@ k,int@H_404_112@ x){
    int@H_404_112@ r=kth(root,k),rr=kth(root,k+1@H_404_112@);
    splay(r,splay(rr,r);
// puts("begin insert <-------------------");@H_404_112@
// printf("%d %d %d\n",rr,tot);@H_404_112@
// debug();@H_404_112@
// puts("end insert <-------------------");@H_404_112@
    newnode(++tot,x,rr);ch[rr][0@H_404_112@]=tot;
    for@H_404_112@(r=rr;r;r=f[r])pushdown(r),pushup(r);
    splay(rr,0@H_404_112@);
}

//删除第k个数@H_404_112@
void@H_404_112@ _delete(int@H_404_112@ k){
    splay(kth(root,k-1@H_404_112@),0@H_404_112@);
    splay(kth(root,k+1@H_404_112@),root);
    delnode(ch[ch[root][1@H_404_112@]][0@H_404_112@]);
    ch[ch[root][1@H_404_112@]][0@H_404_112@]=0@H_404_112@;
    pushup(ch[root][1@H_404_112@]);
    pushup(root);
}

//int get_max(int l,int r){@H_404_112@
// int x=kth(root,l-1),r+1);@H_404_112@
// splay(x,0);splay(y,x);@H_404_112@
// return mx[ch[y][0]];@H_404_112@
//}@H_404_112@

int@H_404_112@ get_min(int@H_404_112@ l,x);
    return@H_404_112@ mi[ch[y][0@H_404_112@]];
}

/*****************************************************/@H_404_112@

char@H_404_112@ s[12@H_404_112@];

int@H_404_112@ main(){
    scanf("%d"@H_404_112@,&n);
    val[1@H_404_112@]=val[n+2@H_404_112@]=1000000000@H_404_112@;
    for@H_404_112@(int@H_404_112@ i=1@H_404_112@+1@H_404_112@;i<=n+1@H_404_112@;i++) val[i]=read();
    tot=n+2@H_404_112@;init(n+2@H_404_112@);
    scanf("%d"@H_404_112@,&m);
    for@H_404_112@(int@H_404_112@ i=1@H_404_112@,d,v;i<=m;i++){
        scanf("%s"@H_404_112@,s);
        if@H_404_112@(s[0@H_404_112@]=='A'@H_404_112@){ //ADD@H_404_112@
            scanf("%d%d%d"@H_404_112@,&l,&r,&d);
            add(l+1@H_404_112@,r+1@H_404_112@,d);
        }
        else@H_404_112@ if@H_404_112@(s[0@H_404_112@]=='I'@H_404_112@){ //INSERT@H_404_112@
            scanf("%d%d"@H_404_112@,&d);
            _insert(l+1@H_404_112@,d);
        }
        else@H_404_112@ if@H_404_112@(s[0@H_404_112@]=='M'@H_404_112@){ //MIN@H_404_112@
            scanf("%d%d"@H_404_112@,&r);
            printf("%d\n"@H_404_112@,get_min(l+1@H_404_112@,r+1@H_404_112@));
        }
        else@H_404_112@ if@H_404_112@(s[0@H_404_112@]=='D'@H_404_112@){ //DELETE@H_404_112@
            scanf("%d"@H_404_112@,&l);
            _delete(l+1@H_404_112@);
        }
        else@H_404_112@ if@H_404_112@(s[3@H_404_112@]=='E'@H_404_112@){ //REVERSE@H_404_112@
            scanf("%d%d"@H_404_112@,&r);
            reversal(l+1@H_404_112@,r+1@H_404_112@);
        }
        else@H_404_112@ { //REVOLVE@H_404_112@
            scanf("%d%d%d"@H_404_112@,&d);
            d=(d%(r-l+1@H_404_112@)+r-l+1@H_404_112@)%(r-l+1@H_404_112@);
            if@H_404_112@(d) exchange(l +1@H_404_112@,r-d +1@H_404_112@,r-d+1@H_404_112@ +1@H_404_112@,r +1@H_404_112@);
        }
// debug();@H_404_112@
    }
// debug();@H_404_112@

    return@H_404_112@ 0@H_404_112@;
}

/**** 5 1 2 3 4 5 6 ADD 1 3 1 INSERT 3 3 DELETE 4 MIN 1 5 MIN 2 5 REVOLVE 1 5 2 10 1 2 3 4 5 6 7 8 9 10 15 ADD 4 8 3 MIN 5 7 MIN 7 10 REVERSE 2 5 MIN 2 6 MIN 2 3 INSERT 3 4 MIN 3 4 MIN 5 10 DELETE 6 MIN 3 5 MIN 4 4 REVOLVE 3 6 7 MIN 5 8 MIN 7 10 // */@H_404_112@

猜你在找的数据结构相关文章