hdu4453Looploop(splay)

제목 여기 찍 어 주세요.
제목: 숫자 꼬치, 길이 n, 앞 뒤 가 연 결 된 것 을 드 립 니 다.첫 번 째 숫자 를 가리 키 는 시퀀스 작업 지침 이 있 습 니 다.m 개 조작, 2 개 인자 k1, k2.6 가지 조작:
1: add x, 현재 포인터 가 있 는 위치 에서 시계 방향 으로 k2 개의 숫자, 각 숫자 에 x 를 추가 합 니 다.
2: reverse, 현재 포인터 가 있 는 위치 부터 시계 방향 k1 개의 숫자 를 뒤 집 습 니 다.
3: insert x, 현재 포인터 다음 위치 에 x 를 추가 합 니 다.
4: delete, 현재 포인터 가 있 는 위치 요 소 를 삭제 합 니 다.
5: move x, x = 1 시 바늘 이 시계 반대 방향 으로 한 자 리 를 이동 하고 x = 2 시 바늘 이 시계 반대 방향 으로 한 자 리 를 이동한다.
6: query, 현재 포인터 가 가리 키 는 요소 값 을 조회 합 니 다.
제목 의 삽화 도 잘 알 고 있다.
제목 분석: splay 의 기본 동작.구체 적 인 실현:
1. 각 노드 마다 누적 값 을 유지 하고 지연 표 시 를 합 니 다.
2. 각 노드 마다 반전 표 시 를 유지 하고 지연 표 시 를 합 니 다.고리 모양 이기 때문에 2 부분 으로 나 눌 수 있 으 며, 해결 방법 은 꼬리 부분 이 부족 하면 서열 머리 를 꼬리 부분 까지 잘라 서 모 아서 뒤 집 는 것 이다.
약 하 다
4. 삭 제 는 간단 합 니 다. 삭 제 된 후에 포인터 위치 가 합 법 적 인지 확인 하 십시오. 링 모양 이기 때문에 시퀀스 의 맨 왼쪽 으로 이동 할 수 있 습 니 다.
약 하 다
6，。。。
코드 가 또 길 게 쓰 여 있 으 니 아 쉬 운 대로 보 세 요 = =!!..
자세 한 내용 은 코드 를 보십시오.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1000005;
const int inf = 0x3f3f3f3f;

int next[N + N];
struct node
{
    int l,r,f,add,lazy,key,size;
}tree[N + N];
int n,m,k1,k2;
void init()
{
    tree[0].size = tree[0].l = tree[0].r = tree[0].f = 0;
    tree[0].add = tree[0].key = tree[0].lazy = 0;
    int nn = N + N;
    for(int i = 0;i < nn;i ++)
        next[i] = i + 1;
}
int newnode()
{
    int p = next[0];
    next[0] = next[p];
    tree[p].lazy = tree[p].add = 0;
    tree[p].l = tree[p].r = tree[p].f = 0;
    tree[p].size = 1;
    return p;
}
void delnode(int p)
{
    next[p] = next[0];
    next[0] = p;
}
void pushup(int rt)
{
    if(rt)
    {
        tree[rt].size = tree[tree[rt].l].size + tree[tree[rt].r].size + 1;
    }
}
void pushdown(int rt)
{
    if(!rt)
        return;
    int ls = tree[rt].l;
    int rs = tree[rt].r;
    if(tree[rt].add)
    {
        if(ls)
        {
            tree[ls].add += tree[rt].add;
            tree[ls].key += tree[rt].add;
        }
        if(rs)
        {
            tree[rs].add += tree[rt].add;
            tree[rs].key += tree[rt].add;
        }
        tree[rt].add = 0;
    }
    if(tree[rt].lazy)
    {
        swap(tree[rt].l,tree[rt].r);
        if(ls)
            tree[ls].lazy ^= 1;
        if(rs)
            tree[rs].lazy ^= 1;
        tree[rt].lazy = 0;
    }
}
void zig(int x)
{
    int p = tree[x].f;
    pushdown(p);
    pushdown(x);
    tree[p].l = tree[x].r;
    if(tree[x].r)
        tree[tree[x].r].f = p;
    pushup(p);
    tree[x].r = p;
    tree[x].f = tree[p].f;
    pushup(x);
    tree[p].f = x;
    if(tree[x].f == 0)
        return;
    if(tree[tree[x].f].l == tree[x].r)
        tree[tree[x].f].l = x;
    else
        tree[tree[x].f].r = x;
}
void zag(int x)
{
    int p = tree[x].f;
    pushdown(p);
    pushdown(x);
    tree[p].r = tree[x].l;
    if(tree[x].l)
        tree[tree[x].l].f = p;
    pushup(p);
    tree[x].l = p;
    tree[x].f = tree[p].f;
    pushup(x);
    tree[p].f = x;
    if(tree[x].f == 0)
        return;
    if(tree[tree[x].f].l == tree[x].l)
        tree[tree[x].f].l = x;
    else
        tree[tree[x].f].r = x;
}
int splay(int x,int goal)
{
    pushdown(x);
    int p;
    while(tree[x].f != goal)
    {
        p = tree[x].f;
        int g = tree[p].f;
        if(g == goal)
        {
            if(tree[p].l == x)
                zig(x);
            if(tree[p].r == x)
                zag(x);
        }
        else
        {
            if(tree[g].l == p && tree[p].l == x)
                zig(p),zig(x);
            else if(tree[g].l == p && tree[p].r == x)
                    zag(x),zig(x);
                else if(tree[g].r == p && tree[p].r == x)
                        zag(p),zag(x);
                    else if(tree[g].r == p && tree[p].l == x)
                            zig(x),zag(x);
        }
    }
    pushup(x);
    return x;
}
int build(int s,int e,int fa)
{
    if(s > e)
        return 0;
    int mid = (s + e)>>1;
    int p = newnode();
    tree[p].l = build(s,mid - 1,p);
    scanf("%d",&tree[p].key);
    tree[p].f = fa;
    tree[p].r = build(mid + 1,e,p);
    pushup(p);
    return p;
}
int getmin(int rt)
{
    pushdown(rt);
    while(tree[rt].l)
    {
        rt = tree[rt].l;
        pushdown(rt);
    }
    return rt;
}
int getmax(int rt)
{
    pushdown(rt);
    while(tree[rt].r)
    {
        rt = tree[rt].r;
        pushdown(rt);
    }
    return rt;
}
int find(int pos,int rt)
{
    if(!rt)
        return 0;
    pushdown(rt);
    if(tree[tree[rt].l].size == pos - 1)
        return rt;
    if(tree[tree[rt].l].size >= pos)
        return find(pos,tree[rt].l);
    else
        return find(pos - tree[tree[rt].l].size - 1,tree[rt].r);
}
void prepare(int &root)
{
    root = newnode();
    tree[root].key = inf;
    tree[root].r = newnode();
    tree[tree[root].r].key = inf;
    tree[tree[root].r].f = root;
    tree[tree[root].r].l = build(1,n,tree[root].r);
    pushup(tree[root].r);
    pushup(root);
    int tmp = getmin(tree[tree[root].r].l);
    root = splay(tmp,0);
}
void Rotate_interval(int a,int b,int &root)
{
    int l = find(a,root);
    int r = find(b + 2,root);
    root = splay(l,0);
    tree[root].r = splay(r,root);
    pushup(tree[root].r);
    pushup(root);
}
void Add(int x,int &root)
{
    int rt,a,b,lefta = 0;
    rt = root;
    if(tree[tree[root].r].size < k2)
        lefta = k2 - tree[tree[root].r].size;
    if(lefta)
    {
        a = tree[tree[root].l].size;
        b = tree[root].size - 2;
        Rotate_interval(a,b,root);
        tree[tree[tree[root].r].l].add += x;
        tree[tree[tree[root].r].l].key += x;
        a = 1;
        b = a + lefta - 1;
        Rotate_interval(a,b,root);
        tree[tree[tree[root].r].l].add += x;
        tree[tree[tree[root].r].l].key += x;
    }
    else
    {
        a = tree[tree[root].l].size;
        b = a + k2 - 1;
        Rotate_interval(a,b,root);
        tree[tree[tree[root].r].l].add += x;
        tree[tree[tree[root].r].l].key += x;
    }
    root = splay(rt,0);
}
void Reverse(int &root)
{
    int a,b,rt,lefta = 0;
    int lsize = tree[tree[root].l].size;
    if(tree[tree[root].r].size < k1)
        lefta = k1 - tree[tree[root].r].size;
    if(lefta)
    {
        a = 1;
        b = lefta;
        Rotate_interval(a,b,root);
        tree[tree[tree[root].r].l].lazy ^= 1;
        a = lefta + 1;
        b = tree[root].size - 2;
        Rotate_interval(a,b,root);
        tree[tree[tree[root].r].l].lazy ^= 1;
        a = 1;b = tree[root].size - 2;
        Rotate_interval(a,b,root);
        tree[tree[tree[root].r].l].lazy ^= 1;
    }
    a = lsize - lefta;
    b = a + k1 - 1;
    Rotate_interval(a,b,root);
    tree[tree[tree[root].r].l].lazy ^= 1;
    rt = find(lsize - lefta + 1,root);
    root = splay(rt,0);
}
void Insert(int x,int &root)
{
    int a = getmin(tree[root].r);
    tree[root].r = splay(a,root);
    int p = newnode();
    tree[p].key = x;
    tree[p].f = tree[root].r;
    tree[tree[root].r].l = p;
    pushup(tree[root].r);
    pushup(root);
}
void Delete(int &root)
{
    int a = getmin(tree[root].r);
    tree[root].r = splay(a,root);
    int p = root;
    tree[tree[root].r].f = 0;
    tree[tree[root].l].f = tree[root].r;
    tree[tree[root].r].l = tree[root].l;
    root = tree[root].r;delnode(p);
    if(tree[root].r == 0)
    {
        a = find(2,root);
        root = splay(a,0);
    }
    pushup(root);
}
void Move(int x,int &root)
{
    int tmp;
    if(x == 1)
    {
        if(tree[tree[root].l].size > 1)
            tmp = getmax(tree[root].l);
        else
            tmp = find(tree[root].size - 1,root);
    }
    else
    {
        if(tree[tree[root].r].size > 1)
            tmp = getmin(tree[root].r);
        else
            tmp = find(2,root);
    }
    root = splay(tmp,0);
}
void Query(int &root)
{
    printf("%d
",tree[root].key);
}
int main()
{
    int x,cas = 0;
    int root;
    char op[20];
    init();
    while(scanf("%d",&n),n)
    {
        scanf("%d%d%d",&m,&k1,&k2);
        prepare(root);
        printf("Case #%d:
",++cas);
        while(m --)
        {
            scanf("%s",op);
            switch(*op)
            {
            case 'a':scanf("%d",&x);Add(x,root);break;
            case 'r':Reverse(root);break;
            case 'i':scanf("%d",&x);Insert(x,root);break;
            case 'd':Delete(root);break;
            case 'm':scanf("%d",&x);Move(x,root);break;
            case 'q':Query(root);break;
            }
        }
    }
    return 0;
}
//218MS	14960K