【Splay】bzoj3223-Tyvj1729文艺平衡树

时间：2021-07-24 07:31:04

一、题目

Description

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字，表示原始序列经过m次变换后的结果

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

顺便附上原题链接→_→Problem 3223. -- Tyvj 1729 文艺平衡树

二、代码实现

裸Splay，基本操作都不齐_(:з」∠)_不过这题有个特点，就是关键字和原序列序号是一样的，所以可以少开一个变量（虽然这并没有什么卵用┑(￣Д ￣)┍

 #include<bits/stdc++.h>

 using namespace std;

 const int MAXN=1e5+;

 int n,m;

 struct node

 {

     int siz,fa,c[];

     bool rev;//翻转标记

 }tr[MAXN];

 int root;

 void push_up(int k)

 {

     tr[k].siz=tr[tr[k].c[]].siz+tr[tr[k].c[]].siz+;

     return;

 }

 void push_down(int k)

 {

     if(tr[k].rev)

     {

         swap(tr[k].c[],tr[k].c[]);

         tr[k].rev=;

         tr[tr[k].c[]].rev^=,tr[tr[k].c[]].rev^=;

     }

     return;

 }

 void rotate(int &k,int x)

 {

     int y=tr[x].fa,z=tr[y].fa;

     bool dy=tr[y].c[]==x,dz=tr[z].c[]==y;

     push_down(y);

     if(k==y)k=x,tr[x].fa=z;

     else tr[z].c[dz]=x,tr[x].fa=z;

     tr[y].c[dy]=tr[x].c[dy^],tr[tr[x].c[dy^]].fa=y;

     tr[x].c[dy^]=y,tr[y].fa=x;

     push_up(y);

     return;

 }

 void splay(int &k,int x)

 {

     push_down(x);

     while(k!=x)

     {

         int y=tr[x].fa,z=tr[y].fa;

         if(k!=y)

         {

             if(tr[y].c[]==x^tr[z].c[]==y)rotate(k,x);

             else rotate(k,y);

         }

         rotate(k,x);

     }

     push_up(x);

     return;

 }

 int find(int k,int x)

 {

     if(!k)return ;

     push_down(k);

     if(x<=tr[tr[k].c[]].siz)return find(tr[k].c[],x);

     if(x==tr[tr[k].c[]].siz+)return k;

     return find(tr[k].c[],x-tr[tr[k].c[]].siz-);

 }

 void print(int k)

 {

     if(!k)return;

     push_down(k);

     print(tr[k].c[]);

     if(k>&&k<n+)printf("%d ",k-);

     print(tr[k].c[]);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     for(int i=;i<=n+;++i)

     {

         tr[i].siz=n+-i;

         tr[i].fa=i-,tr[i].c[]=i+;

     }

     tr[n+].c[]=,root=;

     while(m--)

     {

         int l,r;

         scanf("%d%d",&l,&r);

         splay(root,find(root,l));

         splay(tr[root].c[],find(root,r+));

         tr[tr[tr[root].c[]].c[]].rev^=;

     }

     print(root);

     printf("\n");

     return ;

 }

bzoj3223-文艺平衡树

弱弱地说一句，本蒟蒻码字也不容易，转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/6247021.html

相关文章