首页 > > 程序设计 > C/C++ >

P3391 文艺平衡树

2018-06-17 22:14:42来源：未知阅读 ()

hh

题目描述

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

输入输出格式

输入格式：

第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数

接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

4 3 2 1 5

说明

N,M<=100000

分析

不要问我为什么，我是抄的别人的代码

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<cstdlib>
  7 #include<ctime>
  8 using namespace std;
  9 const int MAXN=300001;
 10 static void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 int ch[MAXN][3];// 0左孩子 1右孩子
 18 int val[MAXN];// 每一个点的权值
 19 int pri[MAXN];// 随机生成的附件权值
 20 int siz[MAXN];// 以i为节点的树的节点数量
 21 int sz;// 总结点的数量 
 22 int n,m;
 23 int x,y,z,a,b,root;
 24 int mark[MAXN];
 25 void update(int x)
 26 {
 27     siz[x]=1+siz[ch[x][0]]+siz[ch[x][1]];
 28 } 
 29 void pushdown(int x)
 30 {
 31     if(x&&mark[x])
 32     {
 33         mark[x]=0;
 34         swap(ch[x][0],ch[x][1]);
 35         if(ch[x][0])    mark[ch[x][0]]^=1;
 36         if(ch[x][1])    mark[ch[x][1]]^=1;
 37     }
 38 }
 39 int new_node(int v)
 40 {
 41     siz[++sz]=1;// 新开辟一个节点
 42     val[sz]=v;
 43     pri[sz]=rand(); 
 44     return sz;
 45 }
 46 
 47 int merge(int x,int y)// 合并 
 48 {
 49     if(!x||!y)    return x+y;// x和y中必定有一个是0
 50     pushdown(x);pushdown(y);
 51     if(pri[x]<pri[y])// 把x加到左边的树上 
 52     {
 53         ch[x][1]=merge(ch[x][1],y);// 不懂的看GIF图 
 54         update(x);
 55         return x;
 56     } 
 57     else
 58     {
 59         ch[y][0]=merge(x,ch[y][0]);
 60         update(y);
 61         return y;
 62     }
 63 }
 64 void split(int now,int k,int &x,int &y)
 65 {
 66     if(!now) x=y=0;// 到达叶子节点
 67     else
 68     {
 69         pushdown(now);
 70         if (k<=siz[ch[now][0]])
 71             y=now,split(ch[now][0],k,x,ch[now][0]);
 72         else
 73             x=now,split(ch[now][1],k-siz[ch[now][0]]-1,ch[now][1],y);
 74         update(now);
 75     } 
 76 }
 77 int build(int l,int r)
 78 {
 79     if(l>r)    return 0;
 80     int mid=(l+r)>>1;int v=mid-1;
 81     int now=new_node(v);
 82     ch[now][0]=build(l,mid-1);
 83     ch[now][1]=build(mid+1,r);
 84     update(now);
 85     //pushdown(now);
 86     return now;
 87 }
 88 void dfs(int x)
 89 {
 90     if(!x)    return ;
 91     pushdown(x);
 92     dfs(ch[x][0]);
 93     if(val[x]>=1&&val[x]<=n)
 94         printf("%d ",val[x]);
 95     dfs(ch[x][1]);
 96 }
 97 void res(int l,int r)
 98 {
 99     int a,b,c,d;
100     split(root,r+1,a,b);
101     split(a,l,c,d);
102     mark[d]^=1;
103     root=merge(merge(c,d),b);
104 }
105 int main()
106 {
107     srand((unsigned)time(NULL));
108     
109     read(n);read(m);
110     root=build(1,n+2);
111     for(int i=1;i<=m;i++)
112     {int l,r;read(l);read(r);res(l,r);}
113     dfs(root);
114     return 0;
115 }