萌田薰子 @ 2018-10-28 22:03:52
为什么强调呢 因为我真的很蒟啊
splay不会区间翻有没有大佬帮忙看看的QAQ
#include <cstdio>
using namespace std;
const int MAXN = 100010;
struct splay {
int son[2],fa,laz;
} e[MAXN];
int ans[MAXN],root,tot;
inline int re()
{
char q = getchar(); int x = 0;
while (q < '0' || q > '9') q = getchar();
while ('0' <= q && q <= '9')
x = (x << 3) + (x << 1) + q - (3 << 4),q = getchar();
return x;
}
inline void build(int l,int r,int f)
{
if (l > r) return;
int mid = (l + r) >> 1;
e[f].son[mid > f] = mid;
e[mid].fa = f;
if (l == r) return;
build(l,mid - 1,mid);
build(mid + 1,r,mid);
}
inline void swap(int x)
{
int bot = e[x].son[0];
e[x].son[0] = e[x].son[1];
e[x].son[1] = bot;
e[e[x].son[0]].laz ^= 1;
e[e[x].son[1]].laz ^= 1;
}
inline void rotate(int x)
{
if (e[x].laz) swap(x);
int y = e[x].fa,z = e[y].fa,mode = e[y].son[0] == x;
e[z].son[e[z].son[1] == y] = x;
e[x].fa = z;
e[y].son[mode ^ 1] = e[x].son[mode];
e[e[x].son[mode]].fa = y;
e[x].son[mode] = y;
e[y].fa = x;
}
inline void splay(int x,int top)
{
while (e[x].fa != top)
{
int y = e[x].fa,z = e[y].fa;
if (z != top) {
if ((e[y].son[0] == x) ^ (e[z].son[0] == y)) rotate(x);
else rotate(y);
}
rotate(x);
}
}
inline void get(int x)
{
if (e[x].laz) swap(x);
if (e[x].son[0]) get(e[x].son[0]);
ans[++tot] = x;
if (e[x].son[1]) get(e[x].son[1]);
}
int main()
{
int n = re(),m = re(),i,j;
root = (n + 3) >> 1;
build(1,n + 2,0);
e[0].son[0] = 0;
e[0].son[1] = 0;
while (m--)
{
int i = re(),j = re();
splay(i,0),root = i;
splay(j + 2,root);
e[e[e[root].son[1]].son[0]].laz ^= 1;
}
get(root);
for (int a = 2 ; a <= n + 1 ; ++ a) printf("%d ",ans[a] - 1);
return 0;
}
by ouuan @ 2018-10-29 19:35:46
@一之濑琴美 kotomichan在自我介绍的时候可不会说错一个字
by 萌田薰子 @ 2018-10-29 20:46:22
@ouuan QAQ不要这样嘲讽了啦