splay poj 3580

//16:38
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x7FFFFFFF
#define maxn 1111111
using namespace std;
int n,que,ll,rr,v,T,id,root,tot,a[maxn],fa[maxn],size[maxn],key[maxn],minv[maxn],del[maxn],rev[maxn],ch[maxn][2];
char opt[11];
void init()
{
    size[0]=fa[0]=0; 
    minv[0]=INF;
}
void update(int x)
{
     size[x]=size[ch[x][0]]+size[ch[x][1]]+1;
     minv[x]=key[x];
     if (ch[x][0]) minv[x]=min(minv[ch[x][0]],minv[x]);
     if (ch[x][1]) minv[x]=min(minv[ch[x][1]],minv[x]);     
}
void pushdown(int x)
{
     if (del[x])
     {
        if (ch[x][0]) { del[ch[x][0]]+=del[x]; minv[ch[x][0]]+=del[x]; key[ch[x][0]]+=del[x]; }
        if (ch[x][1]) { del[ch[x][1]]+=del[x]; minv[ch[x][1]]+=del[x]; key[ch[x][1]]+=del[x]; }
        del[x]=0;
     }
     if (rev[x])
     {
        if (ch[x][0]) rev[ch[x][0]]^=1;
        if (ch[x][1]) rev[ch[x][1]]^=1;
        swap(ch[x][0],ch[x][1]);
        rev[x]=0;        
     }
}
void rotate(int x,int opt) //RR 0 LR 1
{
    int y=fa[x];
    pushdown(y); pushdown(x);
    ch[y][opt]=ch[x][opt^1]; if (ch[x][opt^1]) fa[ch[x][opt^1]]=y;
    fa[x]=fa[y]; if (fa[y]) ch[fa[y]][y==ch[fa[y]][1]]=x;
    fa[y]=x;
    ch[x][opt^1]=y;
    update(y); update(x);
}
void splay(int x,int y)
{
    while (fa[x]!=y)
    { 
        if (fa[fa[x]]==y) rotate(x,x==ch[fa[x]][1]);
           else {
                    if (fa[x]==ch[fa[fa[x]]][0])
                    {
                       if (x==ch[fa[x]][0]) { rotate(fa[x],0); rotate(x,0); }
                          else { rotate(x,1); rotate(x,0); }
                    }
                    else
                    {
                       if (x==ch[fa[x]][1]) { rotate(fa[x],1); rotate(x,1); }
                          else { rotate(x,0); rotate(x,1); }                        
                    }
                }  
    }
    if (!y) root=x;
}
int getpos(int x,int rem)
{
    pushdown(x);
    if (size[ch[x][0]]>=rem) return getpos(ch[x][0],rem);
    if (size[ch[x][0]]+1==rem) return x;
    return getpos(ch[x][1],rem-size[ch[x][0]]-1);
}
void add(int ll,int rr,int d)
{
    int x=getpos(root,ll),y=getpos(root,rr+2);
    splay(x,0);
    splay(y,x);
    del[ch[y][0]]+=d; minv[ch[y][0]]+=d; key[ch[y][0]]+=d;
    update(y);
    update(x); 
}
void reverse(int ll,int rr)
{
    int x=getpos(root,ll),y=getpos(root,rr+2);
    splay(x,0);
    splay(y,x);
    rev[ch[y][0]]^=1; 
}
void revolve(int ll,int rr,int T)
{
    T%=(rr-ll+1);
    if (!T) return;
    T=rr-T;
    reverse(ll,T); reverse(T+1,rr); reverse(ll,rr);
}
void insert(int id,int v)
{
    int x=getpos(root,id+1),y=getpos(root,id+2);
    splay(x,0); splay(y,x);
    key[++tot]=v; minv[tot]=v; size[tot]=1;
    fa[tot]=y;
    ch[y][0]=tot; 
    update(y); update(x);
    splay(tot,0);
}
void remove(int id)
{
    int x=getpos(root,id),y=getpos(root,id+2);
    splay(x,0); splay(y,x);
    ch[y][0]=0; update(y); update(x);
}
int query(int ll,int rr)
{
    int x=getpos(root,ll),y=getpos(root,rr+2);
    splay(x,0); splay(y,x);
    return minv[ch[y][0]];    
}
void addnode(int now,int &x,int fr)
{
    key[++tot]=a[now]; minv[tot]=key[tot];
    size[tot]=1;
    fa[tot]=fr;     
    x=tot;
}
void build(int ll,int rr,int &x,int fr)
{     
     if (ll>rr) return; 
     int mid=(ll+rr)/2;
     addnode(mid,x,fr);
     build(ll,mid-1,ch[x][0],x);
     build(mid+1,rr,ch[x][1],x);
     update(x);
}
int main()
{
    init();
    scanf("%d",&n);
    tot=2; root=1;
    ch[1][1]=2;
    fa[2]=1;
    size[1]=2; size[2]=1; minv[1]=minv[2]=INF;
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,n,ch[2][0],2);
    update(2); update(1);
    scanf("%d",&que);
    for (int i=1;i<=que;i++)
    {
        scanf("%s",opt);    
        switch (opt[0])
        {
           case 'A':
                scanf("%d %d %d",&ll,&rr,&v);  
                add(ll,rr,v);
                break;
           case 'R':
                if (opt[3]=='E') 
                {
                   scanf("%d %d",&ll,&rr);               
                   reverse(ll,rr);                   
                }
                else
                {
                   scanf("%d %d %d",&ll,&rr,&T);
                   revolve(ll,rr,T);
                }
                break;
           case 'I':
                scanf("%d %d",&id,&v);             
                insert(id,v);
                break;
           case 'D':
                scanf("%d",&id);
                remove(id);
                break;
           case 'M':
                scanf("%d %d",&ll,&rr);
                printf("%d\n",query(ll,rr));
                break;
        }     
    }
    return 0;
}

 

转载于:https://wwwblogs/strawberryfgalois/p/4093399.html