蒟蒻(强调这个词)Splay区间翻

P3391 【模板】文艺平衡树

萌田薰子 @ 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-28 22:25:22

@一之濑琴美 Splay存序列时二叉搜索树的大小关系就是序列中的前后关系,第k大就是序列中第k项


by ouuan @ 2018-10-28 22:26:01

@一之濑琴美 而k号节点是原始的第k项,可能由于翻转跑其它地方去了


by 萌田薰子 @ 2018-10-28 22:29:16

@ouuan 这题里面 kth(l - 1) 不就是 l 吗 O_O

这个感觉我没问题吧(心虚) 还有rever是什么意思啊百度解释是河= =


by 萌田薰子 @ 2018-10-28 22:30:24

@ouuan ala ala 我觉得我貌似知道了QAQ 本本本蒟这就去改


by ouuan @ 2018-10-28 22:31:06

@一之濑琴美 (rever是reverseQAQ)


by 萌田薰子 @ 2018-10-28 22:33:57

@ouuan 也就是说我要加一个size数组查对吧(怕错了问一下)


by ouuan @ 2018-10-28 22:36:32

@一之濑琴美 嗯,而且kth的过程中记得下传标记


by 萌田薰子 @ 2018-10-28 22:37:32

@ouuan 好哒 aligado kosaiyimass~


by ouuan @ 2018-10-28 23:15:54

@一之濑琴美 应该是arigatou gozaimasu


by 萌田薰子 @ 2018-10-29 18:50:06

@ouuan QAQ 你总揪人家语病

欺负琴美酱?


上一页 | 下一页