首页 > ACM题库 > HDU-杭电 > HDU 4453-Looploop-模拟-[解题报告]HOJ
2015
07-16

HDU 4453-Looploop-模拟-[解题报告]HOJ

Looploop

问题描述 :

XXX gets a new toy named Looploop. The toy has N elements arranged in a loop, an arrow pointing to one of the elements, and two preset parameters k1 and k2. Every element has a number on it.

Running Rabbits

The figure above shows a Looploop of 6 elments. Let’s assuming the preset parameter k1 is 3, and k2 is 4.
XXX can do six operations with the toy.

1: add x
Starting from the arrow pointed element, add x to the number on the clockwise first k2 elements.

Running Rabbits

2: reverse
Starting from the arrow pointed element, reverse the first k1 clockwise elements.

Running Rabbits

3: insert x
Insert a new element with number x to the right (along clockwise) of the arrow pointed element.

Running Rabbits

4: delete
Delete the element the arrow pointed and then move the arrow to the right element.

Running Rabbits

5: move x
x can only be 1 or 2. If x = 1 , move the arrow to the left(along the counterclockwise) element, if x = 2 move the arrow to the right element.

Running Rabbits

6: query
Output the number on the arrow pointed element in one line.

Running Rabbits

XXX wants to give answers to every query in a serial of operations.

输入:

There are multiple test cases.
For each test case the first line contains N,M,k1,k2(2≤k1<k2≤N≤105, M≤105) indicating the initial number of elements, the total number of operations XXX will do and the two preset parameters of the toy.
Second line contains N integers ai(-104≤ai≤104) representing the N numbers on the elements in Looploop along clockwise direction. The arrow points to first element in input at the beginning.
Then m lines follow, each line contains one of the six operations described above.
It is guaranteed that the "x" in the "add","insert" and "move" operations is always integer and its absolute value ≤104. The number of elements will never be less than N during the operations.
The input ends with a line of 0 0 0 0.

输出:

There are multiple test cases.
For each test case the first line contains N,M,k1,k2(2≤k1<k2≤N≤105, M≤105) indicating the initial number of elements, the total number of operations XXX will do and the two preset parameters of the toy.
Second line contains N integers ai(-104≤ai≤104) representing the N numbers on the elements in Looploop along clockwise direction. The arrow points to first element in input at the beginning.
Then m lines follow, each line contains one of the six operations described above.
It is guaranteed that the "x" in the "add","insert" and "move" operations is always integer and its absolute value ≤104. The number of elements will never be less than N during the operations.
The input ends with a line of 0 0 0 0.

样例输入:

5 1 2 4
3 4 5 6 7
query
5 13 2 4
1 2 3 4 5
move 2
query
insert 8
reverse
query
add 2
query
move 1
query
move 1
query
delete
query
0 0 0 0

样例输出:

Case #1:
3
Case #2:
2
8
10
1
5
1

真的被这道题目恶心到了。。。281行代码。。。比一个模拟题还费事。。。

为了方便起见,在数列的前面和后面都加一个0点。

add x :把第k2+2个点旋转至root1.然后sum[root10]+=x;

reverse:把第k1+2个点旋转至root1.然后rev[root10]^=1;

 insert x:得到第2个点,然后在第2个点之后插入x。

 delete
:把第1个点旋转至root,把第3个点旋转至root1,然后删除root10,然后把1旋转至root

move
1:把第n+1个点删除,然后放入第一个点之后。

move
2:把第2个点删除,然后放入第n+1个点后。

query:直接输出第二个点。

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
#define maxn 1100000
#define mem(a,b) memset(a,b,sizeof(a))
#define root10 ch[ch[root][1]][0]
#define root1 ch[root][1]
#define root11 ch[ch[root][1]][1]
#define lson ch[x][0]
#define rson ch[x][1]
int ch[maxn][2];
int pre[maxn];
int root,tot;
int val[maxn];
int rev[maxn];
int sum[maxn];
int size[maxn];
//----------------------
int num[maxn],n;
void Treaval(int x) {
    if(x) {
        Treaval(ch[x][0]);
        printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]);
        Treaval(ch[x][1]);
    }
}
void debug() {printf("root:%d\n",root);Treaval(root);}
//以上Debug
void init()
{
    root=tot=0;
}
void newnode(int &x,int k,int father)
{
    x=++tot;
    pre[x]=father;
    size[x]=1;
    ch[x][0]=ch[x][1]=0;
    val[x]=k;
    rev[x]=0;
    sum[x]=0;
}
void push_down(int x)
{
    if(sum[x])
    {
        val[lson]+=sum[x];
        val[rson]+=sum[x];
        sum[lson]+=sum[x];
        sum[rson]+=sum[x];
        sum[x]=0;
    }
    if(rev[x])
    {
        rev[x]=0;
        rev[ch[x][0]]^=1;
        rev[ch[x][1]]^=1;
        swap(ch[x][0],ch[x][1]);
    }
}
void push_up(int x)
{
    size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
}
void rot(int x,int kind)
{
    int y=pre[x];
    push_down(y);
    push_down(x);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;
    pre[x]=pre[y];
    ch[x][kind]=y;
    pre[y]=x;
    push_up(y);
    push_up(x);
}
void splay(int x,int goal)
{
    push_down(x);
    while(pre[x]!=goal)
    {
        if(pre[pre[x]]==goal)
        {
            push_down(pre[x]);
            push_down(x);
            rot(x,ch[pre[x]][0]==x);
        }
        else
        {
            int y=pre[x];
            push_down(pre[y]);
            push_down(y);
            push_down(x);
            int kind=ch[pre[y]][0]==y;
            if(ch[y][kind]==x)
            {
                rot(x,!kind);
                rot(x,kind);
            }
            else
            {
                rot(y,kind);
                rot(x,kind);
            }
        }
    }
    push_up(x);
    if(goal==0)root=x;
}

void buildtree(int &x,int l,int r,int father)
{
    if(l>r)return;
    int mid=(l+r)/2;
    newnode(x,num[mid],father);
    buildtree(ch[x][0],l,mid-1,x);
    buildtree(ch[x][1],mid+1,r,x);
    push_up(x);
}

int get_kth(int x,int k)
{
    push_down(x);
    int p=size[ch[x][0]];
    if(p+1==k)return x;
    else if(k<=p)return get_kth(ch[x][0],k);
    else get_kth(ch[x][1],k-p-1);
}

int get_max(int r){
    push_down(r);
    while(ch[r][1]){
        r=ch[r][1];
        push_down(r);
    }
    return r;
}
int get_min(int r){
    push_down(r);
    while(ch[r][0]){
        r=ch[r][0];
        push_down(r);
    }
    return r;
}
void jie(int k)
{
    int x=get_kth(root,k+2);
    splay(x,root);
    push_up(root1);push_up(root);
}
void do_first(int k)
{
    int x=get_kth(root,k+1);
    splay(x,root);
    int z=root10;
    pre[z]=0;ch[x][0]=0;
    push_up(root1);push_up(root);

    int y=get_max(root);
    if(ch[y][0])
    {
        y=get_max(ch[y][0]);
        ch[y][1]=z;pre[z]=y;
    }
    else
    {
        ch[y][0]=z;pre[z]=y;
    }
    while(z)
    {
        push_up(z);
        z=pre[z];
    }
}

void insert(int k,int v)
{
    int x=get_kth(root,k);
   // cout<<k<<"--"<<x<<endl;
    if(ch[x][1]==0)
    {
        newnode(ch[x][1],v,x);
    }
    else
    {
        x=get_min(ch[x][1]);
        newnode(ch[x][0],v,x);
    }
    while(x)
    {
        push_up(x);
        x=pre[x];
    }
    n++;
}
int del(int k)
{
    int x=get_kth(root,k-1);
    int y=get_kth(root,k+1);
    splay(x,0);
    splay(y,root);

    x=root10;
    pre[x]=0;root10=0;
    push_up(root1);push_up(root);
    splay(1,0);
    n--;
    return val[x];
}
void move1()
{
    int x=del(n+1);
    insert(1,x);
}
int move2()
{
    int x=del(2);
    insert(n+1,x);
}
int main()
{
    int m,k1,k2;
    char str[10];
    int x;
    int cas=0;
    while(~scanf("%d%d%d%d",&n,&m,&k1,&k2)&&(n||m||k1||k2))
    {
        cas++;
        init();
        for(int i=1;i<=n;i++)scanf("%d",&num[i]);
        newnode(root,0,0);
        newnode(root1,0,root);
        buildtree(root10,1,n,root1);
        push_up(root1);
        push_up(root);
       printf("Case #%d:\n",cas);
       int pp=0;
        while(m--)
        {
            scanf("%s",str);
            if(str[0]=='a')
            {
                scanf("%d",&x);
                jie(k2);
                sum[root10]+=x;
                val[root10]+=x;
            }
            if(str[0]=='r')
            {
                jie(k1);
                rev[root10]^=1;
            }
            if(str[0]=='i')
            {
                scanf("%d",&x);
                insert(2,x);
            }
            if(str[0]=='d')
            {
                del(2);
            }
            if(str[0]=='m')
            {
                scanf("%d",&x);
                if(x==1)move1();
                if(x==2)move2();
            }
            if(str[0]=='q')
            {
                printf("%d\n",val[get_min(root1)]);
            }
        }
    }
    return 0;
}








版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/rowanhaoa/article/details/30251147