抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

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

Tabris

CSDNPOJ数据结构

发布于：2017年6月20日

次浏览

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

2017-06-20 20:43:37 Tabris_ 阅读数：611

博客爬取于2020-06-14 22:39:58
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/73518838

题目链接：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, 3, 4, 5, 5}
REVERSE x y: reverse the sub-sequence {Ax ... Ay}. For example, performing "REVERSE 2 4" on {1, 2, 3, 4, 5} results in {1, 4, 3, 2, 5}
REVOLVE x y T: rotate sub-sequence {Ax ... Ay} T times. For example, performing "REVOLVE 2 4 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 2, 5}
INSERT x P: insert P after Ax. For example, performing "INSERT 2 4" on {1, 2, 3, 4, 5} results in {1, 2, 4, 3, 4, 5}
DELETE x: delete Ax. For example, performing "DELETE 2" on {1, 2, 3, 4, 5} results in {1, 3, 4, 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, 2, 3, 4, 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这两个节点

翻转

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

旋转

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

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

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

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

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

typedef long long int LL;

const int N = 200000+7;

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

/*******************************************************/

/*************SPLAY-tree************/

int n,m;

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

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

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

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

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

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

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

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

/***************************以下是DEBUG***************************/

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

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

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

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

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

//区间加
void add(int l,int r,int v){
    int x=kth(root,l-1),y=kth(root,r+1);
    splay(x,0);splay(y,x);
    update_add(ch[y][0],v);
}

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

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

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

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

int get_min(int l,int r){
    int x=kth(root,l-1),y=kth(root,r+1);
    splay(x,0);splay(y,x);
    return mi[ch[y][0]];
}

/*****************************************************/

char s[12];

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

    return 0;
}

/****
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

//
*/

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.tabris.top/2017-06-20-73518838/

本页文档最后更新于：2021年5月4日

CSDN

评论