Codechef 12.1 CARDSHUF Splay
题目大意：
有一个长度为$n$的序列，现在要进行$m$个操作，要么将序列中的一段连续子序列换一个位置，要么将这段连续子序列翻转过来再换一个位置。最后输出这个序列。
数据范围$n,m\leq{10^5}$。
算法讨论：
直接利用Splay树维护这些操作即可。
时空复杂度：
时间复杂度$O(n+m\log n)$，空间复杂度$O(n)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
int getc() {
static const int L = 1 << 15;
static char buf[L], *S = buf, *T = buf;
if (S == T) {
T = (S = buf) + fread(buf, 1, L, stdin);
if (S == T)
return EOF;
}
return *S++;
}
int getint() {
static int c, x;
while (!isdigit(c = getc()));
x = c - '0';
while (isdigit(c = getc()))
x = (x << 1) + (x << 3) + c - '0';
return x;
}
#define ls ch[0]
#define rs ch[1]
#define N 100010
struct Node {
Node *ch[2], *pa;
bool rev;
int id, siz;
Node() : siz(0) {}
void revIt() {
swap(ls, rs);
rev ^= 1;
}
void sc(Node *p, bool d) {
ch[d] = p;
p->pa = this;
}
bool d() {
return this == pa->rs;
}
void up() {
siz = ls->siz + 1 + rs->siz;
}
void down();
}mem[N], *G = mem, Tnull, *null = &Tnull, *Root = null;
Node *newnode(int _id) {
G->ls = G->rs = G->pa = null;
G->rev = 0;
G->siz = 1;
G->id = _id;
return G++;
}
void init() {
Root = newnode(0);
Root->sc(newnode(0), 1);
Root->up();
}
void Node::down() {
if (rev) {
if (ls != null)
ls->revIt();
if (rs != null)
rs->revIt();
rev = 0;
}
}
void Rot(Node *p) {
Node *fa = p->pa;
bool d = p->d();
fa->pa->sc(p, fa->d());
fa->sc(p->ch[!d], d);
fa->up();
p->sc(fa, !d);
if (fa == Root)
Root = p;
}
void Splay(Node *p, Node *fa) {
while (p->pa != fa) {
if (p->pa->pa == fa)
Rot(p);
else
Rot(p->d() == p->pa->d() ? p->pa : p), Rot(p);
}
p->up();
}
Node *kth(Node *p, int k) {
while (1) {
p->down();
if (k <= p->ls->siz)
p = p->ls;
else if (k > p->ls->siz + 1)
k -= p->ls->siz + 1, p = p->rs;
else
return p;
}
}
void get(int tl, int tr) {
static Node *p, *q;
p = kth(Root, tl);
Splay(p, null);
q = kth(Root, tr);
Splay(q, p);
}
Node *cutdown(int tl, int tr) {
static Node *re;
get(tl, tr + 2);
re = Root->rs->ls;
Root->rs->ls = null;
Root->rs->up();
Root->up();
return re;
}
void insert(int ins, Node *p) {
get(ins + 1, ins + 2);
Root->rs->sc(p, 0);
Root->rs->up();
Root->up();
}
Node *build(int tl, int tr) {
if (tl > tr)
return null;
int mid = (tl + tr) >> 1;
Node *q = newnode(mid);
q->sc(q->ls = build(tl, mid - 1), 0);
q->sc(q->rs = build(mid + 1, tr), 1);
q->up();
return q;
}
bool ok = 0;
void dfs(Node *p) {
if (p == null)
return;
p->down();
if (p->ls != null)
dfs(p->ls);
if (p->id) {
if (!ok)
ok = 1;
else
putchar(' ');
printf("%d", p->id);
}
if (p->rs != null)
dfs(p->rs);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int n = getint(), m = getint(), a, b, c;
init();
insert(0, build(1, n));
Node *p, *q;
while (m--) {
a = getint();
b = getint();
c = getint();
if (a)
p = cutdown(1, a);
if (b)
q = cutdown(1, b);
if (a)
insert(0, p);
if (c)
p = cutdown(1, c);
if (b) {
q->revIt();
insert(0, q);
}
if (c)
insert(0, p);
}
dfs(Root);
return 0;
}
评论 (0)