Codechef 12.5 TICKETS 图论+最短路+LCA
Codechef 12.9 PARADE 最短路+Floyd+费用流

Codechef 12.1 CARDSHUF Splay

shinbokuow posted @ Dec 02, 2015 02:43:20 PM in Something with tags Splay , 504 阅读

 

题目大意:
有一个长度为$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;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter