poj3580:SuperMemo（塊狀連結清單/Splay）

傳送門

• 題意：

題目要求實作一種資料結構，支援6種操作：

add x,y D：第x個數到第y個數之間的數每個加D；

reverse x y：第x個數到第y個數之間全部數翻轉；

revolve x y T：第x個數到第y個數之間的數，向後循環流動T次，即後面T個數變成這段子序列的最前面T個，前面的被擠到後面。

Insert x P：在第x個數後面插入一個數P。

Delete x：删除第x個數。

Min x，y：求第x個數到第y個數之間的最小數字。

• 題解

1.塊狀連結清單。這是很好想而且很好寫的，全是暴力操作。感興趣的可以自己學習學習。（1400ms）

2.Splay。雖然時間複雜度比塊狀連結清單優（1087ms，其實也沒優什麼，主要是Splay常數大），但是代碼特别長（塊狀連結清單250行，Splay400行）。用Splay主要注意兩點，一是打标記（Add，Reverse操作），二是提取區間（即要操作的區間），提取方法很簡單，将區間前一位置于rt,将區間後一位置于rt的右兒子，那麼對rt右兒子的左兒子操作即可。

主要是Revolve操作有點難寫，下面給出做法：

很顯然是将[r-c+1,r]的區間提取到[l,r-c]之前，那麼先提取前面的區間，再将l-1置為根節點，将l置為l-1的右兒子，将剛才提取的區間置為l左兒子即可。

（注意判斷邊界以及及時更新。。。）

• Code1（塊狀連結清單）：1454MS

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

inline int read(); 
const int N =  + , INF = , SIZEINT = sizeof(int); 
const int SQRTN = , B = , SMIN = SQRTN / , SMAX = SQRTN * ; 
int n, m, a[N]; 

typedef struct Block* PBlock; 
typedef struct List* PList; 
struct Block 
{ 
    int a[SQRTN * ]; 
    int size, tag, rev, ans; 

    inline void calc() 
    { 
        tag = rev = ; ans = INF; 
        for (int i = ; i < size; ++i) 
        if (a[i] < ans) ans = a[i]; 
    } 

    inline void downdate() 
    { 
        if (tag != )
        { 
            for (int i = ; i < size; ++i)a[i] += tag; 
            tag = ; 
        } 
        if (rev)
        { 
            rev = ; 
            for (int i = ; i <<  < size; ++i)
            { 
                int t = a[i]; 
                a[i] = a[size - i - ]; 
                a[size - i - ] = t; 
            } 
        } 
    } 
}used[B]; 

PBlock pool, *top, unused[B]; 
struct List 
{ 
    PBlock a; 
    PList last, next; 
}USED[B]; 

PList head, tail, POOL, *TOP, UNUSED[B]; 

inline PBlock newBlock() 
{ 
    if (top != unused) return *--top; 
    return pool++; 
} 

inline void delBlock(PBlock x) 
{ 
    *top++ = x; 
} 

inline PList newList() 
{ 
    if (TOP != UNUSED) return *--TOP; 
    return POOL++; 
} 

inline void delList(PList x) 
{ 
    *TOP++ = x; 
} 

inline void Build(int *a, const int &n, PList *h, PList *t) 
{ 
    for (int i = ; i < n; i += SQRTN) 
    { 
        PList p = newList(); 
        p->a = newBlock(); 
        p->a->size = i + SQRTN < n ? SQRTN : n - i; 
        memcpy(p->a->a, a + i, SIZEINT * p->a->size); 
        p->a->calc(); 
        p->last = *t; p->next = NULL; 
        if (*t != NULL) (*t)->next = p; 
        else *h = p; 
        *t = p; 
    } 
} 

inline void merge(PList x) 
{ 
    PList p = x->next; 
    x->a->downdate(); 
    p->a->downdate(); 
    memcpy(x->a->a + x->a->size, p->a->a, SIZEINT * p->a->size); 
    x->a->size += p->a->size; 
    x->a->calc(); 
    x->next = p->next; 
    if (p->next) p->next->last = x; 
    else tail = x; 
    delBlock(p->a); 
    delList(p); 
} 

inline void split(PList x, const int &n) 
{ 
    PList p = newList(); 
    p->a = newBlock(); 
    x->a->downdate(); 
    p->a->size = x->a->size - n; 
    memcpy(p->a->a, x->a->a + n, SIZEINT * p->a->size); 
    x->a->size = n; 
    x->a->calc(); 
    p->a->calc(); 
    p->next = x->next; 
    if (x->next) x->next->last = p; 
    else tail = p; 
    x->next = p; p->last = x; 
} 

inline void Balance() 
{ 
    for (PList p = head; p; p = p->next) 
    { 
        while (p != tail && p->a->size < SMIN)merge(p); 
        if (p->a->size > SMAX)split(p, SQRTN); 
    } 
} 

inline void Delete(PList x) 
{ 
    if (x->last != NULL) x->last->next = x->next; 
    else head = x->next; 
    if (x->next != NULL) x->next->last = x->last; 
    else tail = x->last; 
    delBlock(x->a); 
    delList(x); 
} 

inline PList findl(int n) 
{ 
    PList p = head; 
    for (; n > p->a->size; p = p->next) n -= p->a->size; 
    if (n != ) 
    { 
        split(p, n - ); 
        p = p->next; 
    } 
    return p; 
} 

inline PList findr(int n) 
{ 
    PList p = head; 
    for (; n > p->a->size; p = p->next) n -= p->a->size; 
    if (n != p->a->size) split(p, n); 
    return p; 
} 

inline void Init() 
{ 
    pool = used; POOL = USED; 
    top = unused; TOP = UNUSED; 
    head = tail = NULL; 
} 

char ch; 
inline int read() 
{ 
    int res = , sgn = ; 
    while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = ; 
    res = ch - ; 
    while (ch = getchar(), ch >= '0' && ch <= '9') res = res *  + ch - ; 

    return sgn ? -res : res; 
} 

int main() 
{ 
    Init(); 
    n = read(); 
    for (int i = ; i < n; ++i) a[i] = read(); 
    Build(a, n, &head, &tail); 
    m = read(); 
    char type; 
    int l, r, v; 
    PList fr, en, t; 
    PBlock tmp; 
    while (m--) 
    { 
        Balance(); 
        while (type = getchar(), type < 'A' || type > 'Z'); 
        if (type == 'A') 
        { 
            l = read(); r = read(); v = read(); 
            if (l > r) swap(l, r); 
            fr = findl(l); en = findr(r); 
            for (en = en->next; fr != en; fr = fr->next) 
            { 
                fr->a->tag += v; 
                fr->a->ans += v; 
            } 
        } 
        else if (type == 'I') 
        { 
            l = read(); r = read(); 
            fr = findr(l); 
            fr->a->downdate(); 
            fr->a->a[fr->a->size++] = r; 
            if (r < fr->a->ans) fr->a->ans = r; 
        } 
        else if (type == 'D') 
        { 
            l = read(); 
            fr = findl(l); 
            if (fr->a->size != ) 
            split(fr, ); 
            Delete(fr); 
        } 
        else if (type == 'M') 
        { 
            l = read(); r = read(); 
            if (l > r) swap(l, r); 
            fr = findl(l); en = findr(r); 
            int ans = INF; 
            for (en = en->next; fr != en; fr = fr->next) 
            if (fr->a->ans < ans) ans = fr->a->ans; 
            printf("%d\n", ans); 
        } 
        else 
        { 
            getchar(); getchar(); type = getchar(); 
            if (type == 'E') 
            { 
                l = read(); r = read(); 
                if (l > r) swap(l, r); 
                fr = findl(l); en = findr(r); 
                while (fr != en && fr != en->next) 
                { 
                    fr->a->rev ^= ; en->a->rev ^= ; 
                    tmp = fr->a; 
                    fr->a = en->a; 
                    en->a = tmp; 
                    fr = fr->next; 
                    en = en->last; 
                } 
            if (fr == en) fr->a->rev ^= ; 
            } 
            else 
            { 
                l = read(); r = read(); 
                if (l > r) swap(l, r); 
                v = read() % (r - l + ); 
                if (v ==  || l == r) continue; 
                v = r - l +  - v; 
                fr = findl(l); en = findr(r); 
                for (t = fr; v > t->a->size; t = t->next) v -= t->a->size; 
                if (v != t->a->size) 
                { 
                    split(t, v); 
                    if (en == t) en = en->next; 
                } 
                PList p1 = fr->last, p2 = fr, p3 = t, p4 = t->next, p5 = en, 
                p6 = en->next; 
                if (p1 != NULL) 
                { 
                    p1->next = p4; 
                    p4->last = p1; 
                } 
                else head = p4, p4->last = NULL; 
                if (p6 != NULL)
                { 
                    p6->last = p3; 
                    p3->next = p6; 
                } 
                else tail = p3, p3->next = NULL; 
                p5->next = p2; 
                p2->last = p5; 
            } 
        } 
    } 
     return ; 
} 
           

• Code2（Splay）:1047ms

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int Maxn=+;
const int INF=;
inline int read()
{
    char ch=getchar();int i=,f=;
    while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
    while(isdigit(ch)){i=(i<<)+(i<<)+ch-'0';ch=getchar();}
    return i*f;
}

struct node
{
    node *fa,*lc,*rc;
    int val,taga,tagr,mn,sze;
    node():fa(NULL),lc(NULL),rc(NULL){}
    inline void upt()
    {
        sze=(lc?lc->sze:)+(rc?rc->sze:)+;
        mn=min(val,min(lc?lc->mn:INF,rc?rc->mn:INF));
    }
}POOL[Maxn],*pool=POOL,*rt,*que[Maxn];

int n,m,a[Maxn],bg,ed;
char ch[];

inline void add(node *now,int val)
{
    now->val+=val;
    now->mn+=val;
    now->taga+=val;
}

inline void addr(node *now)
{
    swap(now->lc,now->rc);
    now->tagr^=;
}

inline node* newnode(int val)
{
    ++pool;
    pool->val=val;
    pool->mn=val;
    pool->sze=;
    return pool;
}

inline void build(node *&now,int l,int r)
{
    int mid=(l+r)>>;
    now=newnode(a[mid]);
    if(l<mid)build(now->lc,l,mid-);
    if(r>mid)build(now->rc,mid+,r);
    if(now->lc)now->lc->fa=now;
    if(now->rc)now->rc->fa=now;
    now->upt();
}


inline void pushdown(node *now)
{
    if(now->taga)
    {
        if(now->lc)
        {
            now->lc->mn+=now->taga;
            now->lc->val+=now->taga;
            now->lc->taga+=now->taga;
        }
        if(now->rc)
        {
            now->rc->mn+=now->taga;
            now->rc->val+=now->taga;
            now->rc->taga+=now->taga;
        }
        now->taga=;
    }
    if(now->tagr)
    {
        if(now->lc)
        {
            swap(now->lc->lc,now->lc->rc);
            now->lc->tagr^=;
        }
        if(now->rc)
        {
            swap(now->rc->lc,now->rc->rc);
            now->rc->tagr^=;
        }
        now->tagr^=;   
    }
}

inline node* find(node *now,int k)
{
    pushdown(now);now->upt();
    if((now->lc?now->lc->sze:)==k-)return now;
    else if((now->lc?now->lc->sze:)>k-)return find(now->lc,k);
    else return find(now->rc,k-(now->lc?now->lc->sze:)-);
}

inline void Rotate(node *x)
{
    node *y=x->fa,*z=y->fa;
    y->fa=x;x->fa=z;
    if(z){((z->lc==y)?(z->lc):(z->rc))=x;}
    if(y->lc==x)
    {
        node* b=x->rc;
        if(b)b->fa=y;
        y->lc=b;
        x->rc=y;
    }
    else
    {
        node* b=x->lc;
        if(b)b->fa=y;
        y->rc=b;
        x->lc=y;
    }
    y->upt();x->upt();
}

inline bool which(node* x)
{
    return x->fa->lc==x;
}

inline void Splay(node* x,node* tar=NULL)
{
    que[ed=]=x;
    for(node* y=x;y!=rt;y=y->fa)que[++ed]=y->fa;
    for(int i=ed;i>=;i--){node* y=que[i];pushdown(y);}
    while(x->fa!=tar)
    {
        node* y=x->fa,*z=y->fa;
        if(z!=tar)
        {
            if(which(x)^which(y))Rotate(x);
            else Rotate(y);
        }
        Rotate(x);
    }
    if(!tar)rt=x;
}

inline node* split(int l,int r)
{
    if(l&&r<=n)
    {
        node *t1=find(rt,l);
        node *t2=find(rt,r);
        Splay(t1);Splay(t2,rt);
        node *t3=t2->lc;
        t2->lc=NULL;
        t2->upt();
        t3->fa=NULL;
        return t3;
    }
    else if(!l)
    {
        node *t2=find(rt,r);
        Splay(t2);
        node *t3=t2->lc;
        t2->lc=NULL;
        t2->upt();
        t3->fa=NULL;
        return t3;
    }
    else
    {
        node *t1=find(rt,l);
        Splay(t1);
        node *t3=t1->rc;
        t3->fa=NULL;
        t1->rc=NULL;
        t1->upt();
        return t3;
    }
}

int buf[];
inline void W(int x)
{
    if(!x){putchar('0');return;}
    if(x<)putchar('-'),x=-x;
    while(x)buf[++buf[]]=x%,x/=;
    while(buf[])putchar('0'+buf[buf[]--]);
    return;
}

int main()
{
    n=read();
    for(int i=;i<=n;i++){a[i]=read();}
    build(rt,,n);
    m=read();
    while(m--)
    {
        scanf("%s",ch+);
        if(ch[]=='A')
        {
            int l=read(),r=read(),v=read();
            if(l==&&r==n)add(rt,v);
            else if(l==)
            {
                node* t2=find(rt,r+);
                Splay(t2);
                add(rt->lc,v);
                rt->upt();
            }
            else if(r==n)
            {
                node* t1=find(rt,l-);
                Splay(t1);
                add(rt->rc,v);
                rt->upt();
            }
            else 
            {
                node* t1=find(rt,l-);
                node* t2=find(rt,r+);
                Splay(t1);
                Splay(t2,rt);
                add(t2->lc,v);
                t2->upt();t1->upt();
            }
        }
        else if(ch[]=='I')
        {
            int x=read(),y=read();
            if(x!=&&x!=n)
            {
                node* t1=find(rt,x);
                node* t2=find(rt,x+);
                Splay(t1);
                Splay(t2,rt);
                t2->lc=newnode(y);
                t2->lc->fa=t2;
                t2->upt();t1->upt();
                n++;
            }
            else if(x!=)
            {
                node* t1=find(rt,x);
                Splay(t1);
                t1->rc=newnode(y);
                t1->rc->fa=t1;
                t1->upt();
                n++;
            }
            else
            {
                node* t2=find(rt,x+);
                t2->lc=newnode(y);
                t2->lc->fa=t2;
                t2->upt();
                n++;
            }       
        }
        else if(ch[]=='D')
        {
            int pos=read();
            if(pos!=&&pos!=n)
            {
                node* t1=find(rt,pos-);
                node* t2=find(rt,pos+);
                Splay(t1);
                Splay(t2,rt);
                t2->lc->fa=NULL;
                t2->lc=NULL;
                t2->upt();
                rt->upt();
                n--;
            }
            else if(pos!=)
            {
                node* t1=find(rt,pos-);
                Splay(t1);
                t1->rc->fa=NULL;
                t1->rc=NULL;
                t1->upt();
                n--;
            }
            else
            {
                node* t2=find(rt,pos+);
                Splay(t2);
                t2->lc->fa=NULL;
                t2->lc=NULL;
                t2->upt();
                n--;
            }
        }
        else if(ch[]=='M')
        {
            int l=read(),r=read();
            if(l==&&r==n)W(rt->mn),putchar('\n');
            else if(l==)
            {
                node* t2=find(rt,r+);
                Splay(t2);
                W(rt->lc->mn),putchar('\n');
            }
            else if(r==n)
            {
                node* t1=find(rt,l-);
                Splay(t1);
                W(rt->rc->mn),putchar('\n');
            }
            else 
            {
                node* t1=find(rt,l-);
                node* t2=find(rt,r+);
                Splay(t1);
                Splay(t2,rt);
                W(t2->lc->mn),putchar('\n');
            }
        }
        else if(ch[]=='E')
        {
            int l=read(),r=read();
            if(l==&&r==n)addr(rt);
            else if(l==)
            {
                node* t2=find(rt,r+);
                Splay(t2);
                addr(rt->lc);
            }
            else if(r==n)
            {
                node* t1=find(rt,l-);
                Splay(t1);
                addr(rt->rc);
            }
            else 
            {
                node* t1=find(rt,l-);
                node* t2=find(rt,r+);
                Splay(t1);
                Splay(t2,rt);
                addr(t2->lc);
            }
        }
        else
        {
            int x=read(),y=read(),c=read();
            int l=(y-x+);
            c%=l;
            if(c==)continue;
            node* t1=split(y-c,y+);
            if(x!=)
            {
                node* t2=find(rt,x-);
                node* t3=find(rt,x);
                Splay(t2);
                Splay(t3,rt);
                t3->lc=t1;
                t1->fa=t3;
                t3->upt();
                t2->upt();
            }
            else
            {
                node* t3=find(rt,x);
                Splay(t3);
                t3->lc=t1;
                t1->fa=t3;
                t3->upt();
            }
        }
    }
}