[BZOJ3223]Tyvj 1729 文艺平衡树

发布时间:2017-2-23 22:28:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[BZOJ3223]Tyvj 1729 文艺平衡树 ",主要涉及到[BZOJ3223]Tyvj 1729 文艺平衡树 方面的内容,对于[BZOJ3223]Tyvj 1729 文艺平衡树 感兴趣的同学可以参考一下。

[BZOJ3223]Tyvj 1729 文艺平衡树

试题描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1 

输入

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n 

输出

输出一行n个数字,表示原始序列经过m次变换后的结果 

输入示例

5 31 31 31 4

输出示例

4 3 2 1 5 

数据规模及约定

N,M<=100000

题解

裸 splay,注意最后要多输出一个空格。

#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cctype>#include <algorithm>using namespace std;int read() {	int x = 0, f = 1; char c = getchar();	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }	return x * f;}#define maxn 100010struct Node {	int v, siz; bool rev;	Node() {}	Node(int _): v(_), rev(0) {}} ns[maxn];int rt, ToT, fa[maxn], ch[2][maxn];void maintain(int o) {	ns[o].siz = 1;	for(int i = 0; i < 2; i++) if(ch[i][o])		ns[o].siz += ns[ch[i][o]].siz;	return ;}void build(int& o, int l, int r) {	if(l > r) return ;	int mid = l + r >> 1;	ns[o = ++ToT] = Node(mid);	if(l == r) return maintain(o);	build(ch[0][o], l, mid - 1); build(ch[1][o], mid + 1, r);	if(ch[0][o]) fa[ch[0][o]] = o;	if(ch[1][o]) fa[ch[1][o]] = o;	return maintain(o);}void pushdown(int o) {	for(int i = 0; i < 2; i++) if(ch[i][o])		ns[ch[i][o]].rev ^= ns[o].rev;	if(ns[o].rev) swap(ch[0][o], ch[1][o]), ns[o].rev = 0;	return ;}void rotate(int u) {	int y = fa[u], z = fa[y], l = 0, r = 1;	if(z) ch[ch[1][z]==y][z] = u;	if(ch[1][y] == u) swap(l, r);	fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;	ch[l][y] = ch[r][u]; ch[r][u] = y;	maintain(y); maintain(u);	return ;}int S[maxn], top;void splay(int u) {	int t = u; S[++top] = t;	while(fa[t]) t = fa[t], S[++top] = t;	while(top) pushdown(S[top--]);	while(fa[u]) {		int y = fa[u], z = fa[y];		if(z) {			if(ch[0][y] == u ^ ch[0][z] == y) rotate(u);			else rotate(y);		}		rotate(u);	}	return ;}int split(int u) {	if(!u) return 0;	splay(u);	int tmp = ch[1][u];	fa[tmp] = 0; ch[1][u] = 0;	maintain(u);	return tmp;}int merge(int a, int b) {	if(!a) return maintain(b), b;	if(!b) return maintain(a), a;	pushdown(a); while(ch[1][a]) a = ch[1][a], pushdown(a);	splay(a);	ch[1][a] = b; fa[b] = a;	return maintain(a), a;}int qkth(int o, int k) {	if(!o) return 0;	pushdown(o);	int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;	if(k == ls + 1) return o;	if(k > ls + 1) return qkth(ch[1][o], k - ls - 1);	return qkth(ch[0][o], k);}int Find(int k) {	rt = 1; while(fa[rt]) rt = fa[rt];	return qkth(rt, k);}void Rev(int ql, int qr) {	int lrt = Find(ql - 1), mrt = Find(qr), rrt;	split(lrt); rrt = split(mrt);	ns[mrt].rev ^= 1;	mrt = merge(lrt, mrt); merge(mrt, rrt);	return ;}int main() {	int n = read(), q = read();		build(rt, 1, n);	while(q--) {		int l = read(), r = read();		Rev(l, r);	}		for(int i = 1; i <= n; i++) {		int k = Find(i);		printf("%d ", ns[k].v);	}		return 0;}

上一篇:yield 用法分析
下一篇:企业shell面试题:获取51CTO博客列表倒序排序考试题

相关文章

相关评论