poj 3580 SuperMemo(splay豊富な操作)

11354 ワード
データ構造 splay
SuperMemo
Time Limit: 5000 MS
 
メモリLimit: 65536 K
Total Submissions: 6668
 
Acceepted: 2226
Case Time Limit: 2000 MS
Description
Your friend、Jackson is invited to a TV show caled Super Memo in which the particent is told to play a memorizing game.At first、the host tells the participad a sequence of numberss、｛A 1、A 1 A 2,… An.Then the host performs a series of operations and queries on the sequence which consists:
  • ADD x D:Add D to each number in sub-sequence{Ax ... Ay].For example,performing“ADD” 2 4“on｛1,2,3,4,5｝レスルツin｛1,3,4,5,5｝
  • REVERSE x y:reverse the sub-sequence{Ax ... Ay].For example,performing“REVERSE” 2"on{1,2,3,4,5}reults in{1,4,3,2,5}
  • REVOLVE x T:rotate sub-sequence｛Ax ... Ay｝ T times.For example,performing"REVOLVE" 2 2「on｛1,2,3,4,5｝reults in｛1,3,4,2,5｝
  • INSERT x P:insert P アフターサービス Ax.For example、performing"INSERT" 2"on{1,2,3,4,5}reults in{1,2,4,3,4,5}
  • DELETE x:delete Ax.For example,performing“DELETE” 2“on｛1,2,3,4,5｝reults in｛1,3,4,5｝
  • MIN x y:query the participnt what is the minimum number in sub-sequence{Ax ... Ay].For example,the corect answer to“MIN” 2"on{1,2,3,4,5}is 2
    • To make the show more interesting,the particent is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query hermy cal you for help.You task to is watthe TV proreders
    Input
    The first line contains n (n ≤100000).
    The follwing n lines describe the sequence.
    The n follows M (M ≦100000)、the numbers of operations and queries.
    The follwing M lines describe the operations and queries.
    Output
    For each“MIN”query,output the corect answer.
    Sample Input
    5
1 
2 
3 
4 
5
2
ADD 2 4 1
MIN 4 5
    Sample Output
    5
    ソurce
    POJ Founder Monthly Conttest–2008.04.13,Yao Jinyu
    まず午前中をコードして、午後＋一晩調整して、やっと過ぎました.牛は満面ですね.
    splayも入門ですよね.splayはやはり強大で、各種の神の操作はすべて言うまでもありません.
    タイトル:シーケンスを一つください.6つの操作:
    1、ADD a b c:区間[a,b]を全部cとする.
    2、RESERVE a b:区間[a,b]を反転させる;
    3、REVOLVE a b c:区間[a,b]を右にcビット移動します.(題目の説明はよく分かりませんが、yyでも大丈夫です.Cはマイナスの場合があります.左にシフトすることがあります.)
    4、DEL a:a番目の位置の数を削除する.
    5、INSERT a b:a番目の数の後に数bを加える.
    6、MIN a b:問い合わせ区間[a,b]の最小値.
    操作が豊富ですね.
    テーマ分析:すべての操作を逐一分析する:
    1、通常の操作で、lazyマークでOKです.
    2、通常の操作で、lazyマークで大丈夫です.
    3、循環右シフト操作は、まず右シフト長さを区間長に対して型を取り、実際の右シフト長cを得て、区間を2つの部分に分けます.［a,a＋c-1］、［a＋c,b］、右シフトの実効効果は、実際には前の2つの区間を交換します.
    もっと簡単なやり方があります.REVOLVE[a,b]=REVERSE[a,b]+REVERSE[a,a+c-1]+REVERE[a+c,b]があります.
    4、削除操作は、削除するノードsplayをツリーの根元に送り、削除するノードの次のノードsplayをルートの右サブツリーに送り、ツリーの根を削除して、左右のツリーを統合すれば良い.
    5、挿入動作は、aノードsplayをツリーの根元に、a＋1ノードsplayをルートの右サブツリーに、新規ノードを右サブツリーの左サブツリーに挿入する.
    6、照会操作は、説明しません.
    詳細はコードを参照してください:
    #include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100005;
const int INF = 0x7fffffff;
int m,n;
int next[N + N];
struct node
{
    int l,r,f,mn,add,lazy,key,size;
}tree[N + N];
int Min(int a,int b)
{
    return a > b?b:a;
}

void show(int rt)
{
	if(rt)
	{
		show(tree[rt].l);
		printf("  %2d:    %2d     %2d     %2d key = %2d size = %2d ,mn = %2d
    ",rt,tree[rt].l,tree[rt].r,tree[rt].f,tree[rt].key,tree[rt].size,tree[rt].mn);
		show(tree[rt].r);
	}
}
void debug(int rt)
{
	printf("root: %d
    ",rt);
	show(rt);
}
void init()
{
    tree[0].size = tree[0].lazy = tree[0].add = 0;
    tree[0].key = tree[0].mn = INF;
    for(int i = 0;i < N + N;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 = tree[p].mn = 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;
        tree[rt].mn = Min(tree[rt].key,Min(tree[tree[rt].l].mn,tree[tree[rt].r].mn));
    }
}

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;
			tree[ls].mn += tree[rt].add;
		}
        if(rs)
        {
			tree[rs].add += tree[rt].add;
			tree[rs].mn += 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[p].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;//parent
    while(tree[x].f != goal)
    {
        p = tree[x].f;
        int g = tree[p].f;//grandparent
        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)//ll
            {
                zig(p);
                zig(x);
            }
            else if(tree[g].l == p && tree[p].r == x)//lr
            {
                zag(x);
                zig(x);
            }
            else if(tree[g].r == p && tree[p].r == x)//rr
            {
                zag(p);
                zag(x);
            }
            else if(tree[g].r == p && tree[p].l == x)//rl
            {
                zig(x);
                zag(x);
            }
        }
    }
    pushup(x);
    return x;
}

int build(int l,int r,int fa)
{
    if(l > r)
        return 0;
    int mid = (l + r)>>1;
    int p = newnode();
    tree[p].l = build(l,mid - 1,p);
    scanf("%d",&tree[p].key);
    tree[p].mn = tree[p].key;
    tree[p].f = fa;
    tree[p].r = build(mid + 1,r,p);
    pushup(p);
    return p;
}

void prepare(int &root)
{
    root = newnode();//       ，      1  
    tree[root].mn = INF;
    tree[root].key = INF;
    tree[root].r = newnode();
    tree[tree[root].r].mn = INF;
    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 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);
}

int getMax(int rt)
{
    pushdown(rt);
    while(tree[rt].r)
    {
        rt = tree[rt].r;
        pushdown(rt);
    }
    return rt;
}

int getMin(int rt)
{
    pushdown(rt);
    while(tree[rt].l)
    {
        rt = tree[rt].l;
        pushdown(rt);
    }
    return rt;
}

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 a,int b,int c,int &root)
{
    Rotate_interval(a,b,root);
    tree[tree[tree[root].r].l].add += c;
	tree[tree[tree[root].r].l].mn += c;
	tree[tree[tree[root].r].l].key += c;
}

void Reverse(int a,int b,int &root)
{
    Rotate_interval(a,b,root);
    tree[tree[tree[root].r].l].lazy ^= 1;
}

void Revolve(int a,int b,int c,int &root)//    
{
    Rotate_interval(a,b,root);
    int len = b - a + 1;
    c = (c % len + len) % len;
    if(c == 0)
        return;
    c = len - c;
//    Reverse(a,a + c - 1,root);          3     
//    Reverse(a + c,b,root);           
//    Reverse(a,b,root);              ：
    int p = find(c + 1,tree[tree[root].r].l);//tree[tree[root].r].l      root
    tree[tree[root].r].l = splay(p,tree[root].r);//        c+1  splay    root
    int tmp = tree[tree[tree[root].r].l].l;//       root            
    tree[tree[tree[root].r].l].l = 0;//             ，      ，      ok
    int nt = getMax(tree[tree[root].r].l);
    tree[tree[root].r].l = splay(nt,tree[root].r);
    tree[tree[tree[root].r].l].r = tmp;
    tree[tmp].f = tree[tree[root].r].l;
    pushup(tree[tree[root].r].l);
    pushup(tree[root].r);
    pushup(root);
}

void Insert(int a,int b,int &root)
{
    int p = newnode();
    tree[p].mn = b;
    tree[p].key = b;
    int x = find(a + 1,root);
    root = splay(x,0);
    x = find(a + 2,root);
    tree[root].r = splay(x,root);
    tree[p].f = tree[root].r;
    tree[tree[root].r].l = p;
    root = splay(p,0);
    pushup(root);
}

void Del(int a,int &root)
{
    int x = find(a + 1,root);
    root = splay(x,0);
    x = find(a + 2,root);
    tree[root].r = splay(x,root);
    tree[tree[root].l].f = tree[root].r;
    tree[tree[root].r].l = tree[root].l;
    x = root;
    root = tree[x].r;
    delnode(x);
    tree[root].f = 0;
    pushup(root);
}

void Min_query(int a,int b,int &root)
{
    Rotate_interval(a,b,root);
    printf("%d
    ",tree[tree[tree[root].r].l].mn);
}

int main()
{
    int root;
    int a,b,c;
    char op[20];
    while(scanf("%d",&n) != EOF)
    {
        init();
        prepare(root);
		scanf("%d",&m);
        while(m --)
        {
            scanf("%s",op);
            scanf("%d",&a);
            switch(*op)
            {
            case 'A':
                scanf("%d%d",&b,&c);
                Add(a,b,c,root);break;
            case 'R':
                if(op[3] == 'E')
                {
                    scanf("%d",&b);
                    Reverse(a,b,root);
                }
                else
                {
                    scanf("%d%d",&b,&c);
                    Revolve(a,b,c,root);
                }
                break;
            case 'I':
                scanf("%d",&b);
                Insert(a,b,root);
                break;
            case 'D':Del(a,root);break;
            case 'M':
                scanf("%d",&b);
                Min_query(a,b,root);
            }
        }
    }
    return 0;
}
//4612K	750MS
/*
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
5 1 2 3 4 5
14
MIN 1 1
MIN 2 2
MIN 3 3
MIN 4 4
MIN 5 5
REVOLVE 2 5 2
REVERSE 2 3
REVERSE 4 5
REVERSE 2 5
MIN 1 1
MIN 2 2
MIN 3 3
MIN 4 4
MIN 5 5

8 1 2 3 4 5 6 7 8
30
MIN 2 7
ADD 5 6 -7
MIN 2 7
REVERSE 3 8
MIN 6 8
REVOLVE 1 6 -9
MIN 1 3
DEL 3
MIN 2 4
INSERT 7 5
MIN 5 8
REVOLVE 2 8 11
MIN 6 8
MIN 1 2
ADD 1 2 -5
MIN 1 2
*/
    Fabric取引データ構造