迷人的拉伸树、、、

他们是非常光秃秃的树拉伸操作。没有技术含量。

注意下放时标记的样子。。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define LL long long#define maxn 220000#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]#define INF ~0u>>2int ch[maxn][2];int pre[maxn];int root,tot;int size[maxn];int val[maxn];int rev[maxn];int lazy[maxn];int minn[maxn];//----------------------int num[maxn];int st[maxn];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);}void debug2(){    puts("start:");    for(int x=1;x<=tot;x++)    {            printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,key = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x]);    }}//以上Debugvoid push_down(int x){    if(lazy[x])    {        if(lson)        {            lazy[lson]+=lazy[x];            val[lson]+=lazy[x];            minn[lson]+=lazy[x];        }        if(rson)        {            lazy[rson]+=lazy[x];             val[rson]+=lazy[x];             minn[rson]+=lazy[x];        }        lazy[x]=0;    }    if(rev[x])    {        rev[lson]^=1;        rev[rson]^=1;        swap(lson,rson);        rev[x]=0;    }}void push_up(int x){    size[x]=size[lson]+size[rson]+1;    minn[x]=val[x];    if(lson)minn[x]=min(minn[x],minn[lson]);    if(rson)minn[x]=min(minn[x],minn[rson]);}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 init(){    root=tot=0;    size[0]=0;    memset(ch,0,sizeof(ch));    memset(pre,0,sizeof(pre));}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]=lazy[x]=0;    minn[x]=k;   // printf("val[%d]=%d,st[%d]=%d\n",x,k,k,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;}int main(){    int n,x;    int cas=0;     int q,a,b,c;    while(~scanf("%d",&n))    {        for(int i=1;i<=n;i++)        {            scanf("%d",&num[i]);        }        init();        newnode(root,INF,0);        newnode(root1,INF,root);        size[root]=2;        buildtree(root10,1,n,root1);        push_up(root1);push_up(root);        scanf("%d",&q);        char str[110];        //cout<
          
           <<" "<
           
            <
            
             b)swap(a,b); int x=get_kth(root,a); int y=get_kth(root,b+2); splay(x,0); splay(y,root); lazy[root10]+=c; val[root10]+=c; minn[root10]+=c; } else if(str[0]=='R'&&str[3]=='E') { scanf("%d%d",&a,&b); if(a>b)swap(a,b); int x=get_kth(root,a); int y=get_kth(root,b+2); splay(x,0); splay(y,root); rev[root10]^=1; } else if(str[0]=='R'&&str[3]=='O') { scanf("%d%d%d",&a,&b,&c); if(a>b)swap(a,b); int m=b-a+1; c=c%m;c=(c+m)%m; if(c==0)continue; int x=get_kth(root,a); int y=get_kth(root,a+1); int xx=get_kth(root,b-c+1); int yy=get_kth(root,b+2); splay(xx,0); splay(yy,root); int ps=root10; root10=0; push_up(root1);push_up(root); splay(x,0); splay(y,root); root10=ps; pre[ps]=root1; push_up(root1);push_up(root); } else if(str[0]=='I') { scanf("%d%d",&a,&b); int x=get_kth(root,a+1); int y=get_kth(root,a+2); splay(x,0); splay(y,root); newnode(root10,b,root1); push_up(root1);push_up(root); } else if(str[0]=='D') { scanf("%d",&a); int x=get_kth(root,a); int y=get_kth(root,a+2); splay(x,0); splay(y,root); root10=0; push_up(root1); push_up(root); } else if(str[0]=='M') { scanf("%d%d",&a,&b); if(a>b)swap(a,b); int x=get_kth(root,a); int y=get_kth(root,b+2); splay(x,0); splay(y,root); printf("%d\n",minn[root10]); } } } return 0;}
            
           
          
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。