NC210157. 文艺平衡树
描述
输入描述
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
输出描述
输出一行n个数字，表示原始序列经过m次变换后的结果
示例1
输入:
200 50 57 184 29 105 1 100 4 76 9 104 19 87 25 118 37 136 39 166 55 170 133 169 23 154 25 102 47 136 17 37 43 122 31 116 12 113 35 146 29 143 53 140 39 160 5 104 157 193 5 57 55 65 11 136 55 122 53 138 15 84 49 95 3 127 56 149 35 104 71 159 23 96 37 120 6 95 28 107 63 181 3 30 57 105 27 96 29 154 12 85 121 194 7 84 39 164 5 120 13 98
输出:
34 35 107 108 45 177 41 70 18 87 88 89 92 168 144 158 159 123 124 125 126 127 171 170 64 65 66 67 149 148 147 146 145 154 6 134 105 23 141 122 121 120 119 118 117 116 115 46 47 48 49 50 51 52 53 10 9 8 7 153 152 151 150 97 98 99 100 194 143 157 156 33 167 166 165 164 163 162 161 160 142 79 80 81 82 83 84 85 86 19 128 25 36 90 71 72 73 74 93 94 95 96 68 69 17 37 24 106 75 76 182 13 14 15 16 38 39 40 176 109 44 43 42 91 11 54 55 56 184 183 12 1 2 3 4 172 26 27 28 136 30 31 32 155 174 111 112 113 114 178 179 137 29 135 104 103 102 101 193 192 191 110 175 169 63 62 61 60 59 58 57 185 186 187 188 189 190 173 5 133 132 131 130 129 20 21 22 140 139 138 180 181 77 78 195 196 197 198 199 200
说明:
N,M<=100000C++(clang++ 11.0.1) 解法, 执行用时: 292ms, 内存消耗: 3300K, 提交时间: 2022-09-20 20:27:41
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
struct Tree{
int l,r;
int key,val,tag,sz;
}tr[N];
int rt,idx;
mt19937 g(0);
int newnode(int v)
{
tr[++idx].val=v,tr[idx].key=g(),tr[idx].sz=1;
return idx;
}
void pu(int x)
{
tr[x].sz=tr[tr[x].l].sz+tr[tr[x].r].sz+1;
}
void calc(int x)
{
swap(tr[x].l,tr[x].r);
tr[x].tag^=1;
}
void pd(int x)
{
if(tr[x].tag)
{
tr[x].tag^=1;
calc(tr[x].l);
calc(tr[x].r);
}
}
void split(int p,int k,int &x,int &y)
{
if(!p) x=y=0;
else
{
pd(p);
if(tr[tr[p].l].sz<k)
{
x=p;
split(tr[p].r,k-tr[tr[p].l].sz-1,tr[x].r,y);
}
else
{
y=p;
split(tr[p].l,k,x,tr[y].l);
}
pu(p);
}
}
int merge(int x,int y)
{
if(!x||!y) return x|y;
if(tr[x].key<tr[y].key)
{
pd(x);
tr[x].r=merge(tr[x].r,y);
pu(x);
return x;
}
else
{
pd(y);
tr[y].l=merge(x,tr[y].l);
pu(y);
return y;
}
}
void print(int rt)
{
if(!rt) return;
pd(rt);
print(tr[rt].l);
cout<<tr[rt].val<<" ";
print(tr[rt].r);
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) rt=merge(rt,newnode(i));
for(int i=1,l,r;i<=m;i++)
{
cin>>l>>r;
int x,y,z;
split(rt,l-1,x,y);
split(y,r-l+1,y,z);
tr[y].tag^=1;
swap(tr[y].l,tr[y].r);
rt=merge(merge(x,y),z);
}
print(rt);
return 0;
}