您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是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:
5 3
1 3
1 3
1 4
输出样例#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 }