UVa 11922 Permutation Transformer splay 把序列翻转后放到结尾

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18902

题意：给定原始序列 1-n ，m个操作，每次把区间[u,v]的数 翻转后放到序列结尾，最后中序遍历输出序列

第一发手打splay

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;
#define ll long long
#define N 100105
#define inf 100000000
#define L(id) tree[id].ch[0]
#define R(id) tree[id].ch[1]
#define Father(id) tree[id].fa
ll Mid(ll x, ll y){return (x+y)/2;}

struct Node{
	ll ch[2], fa, size;
	ll num;
	bool filp;
}tree[N];
ll tot, root;
void Newnode(ll& id, ll fa, ll val){
	id = ++tot;
	Father(id) = fa;
	tree[id].num = val;
	tree[id].size = 1;
	L(id) = R(id) = 0;
	tree[id].filp = 0;
}
void push_up(ll id){
	tree[id].size = tree[L(id)].size + tree[R(id)].size +1;
}
void push_down(ll id){
	if(tree[id].filp){
		tree[L(id)].filp ^= 1;
		tree[R(id)].filp ^= 1;
		swap(L(id), R(id));
		tree[id].filp = 0;
	}
	return ;
}
void Rotate(ll x, ll kind){// 0 代表左旋 1代表右旋 0:x在右子树 1:x在左子树
	ll y = Father(x);
	push_down(x); push_down(y);
	tree[y].ch[kind^1] = tree[x].ch[kind];
	Father(tree[x].ch[kind]) = y;

	if(Father(y))
		tree[Father(y)].ch[R(Father(y))==y] = x;
	Father(x) = Father(y);

	tree[x].ch[kind] = y;
	Father(y) = x;
	push_up(y);
}
void Splay(ll id, ll goal){
	push_down(id);
	while(Father(id)!=goal){
		ll y = Father(id);
		if(Father(y) == goal)
			Rotate(id, L(y)==id);
		else {
			ll kind = L(Father(y)) == y; //1表示y是左子树
			if(tree[y].ch[kind] == id)
			{ //不共线
				Rotate(id, kind^1);
				Rotate(id, kind);
			}
			else 
			{
				Rotate(y, kind);
				Rotate(id, kind);
			}
		}
	}
	push_up(id);
	if(goal == 0) root = id;
}
ll Get_kth(ll k){ //找到第k大的数
	int id = root;
	push_down(id);
	while(tree[L(id)].size!=k){
		if(tree[L(id)].size>k)
			id = L(id);
		else {
			k -= (tree[L(id)].size + 1);
			id = R(id);
		}
		push_down(id);
	}
	return id;
}
void RotateTo(ll l, ll r){
	Splay(Get_kth(l-1), 0);
	Splay(Get_kth(r+1), root);
}
void RotateMin(ll v, ll goal){
	int id = root;
	push_down(id);
	while(tree[id].num != v){
		if(tree[L(id)].num == v)
			id = L(id);
		else 
			id = R(id);
		push_down(id);
	}
	Splay(id, goal);
}

void build(ll l, ll r, ll &id, ll fa){
	if(l > r)return;
	ll mid = Mid(l,r);
	Newnode(id, fa, mid);
	build(l, mid-1, L(id), id);
	build(mid+1, r, R(id), id);
	push_up(id);
}
ll getMax(ll id){
	push_down(id);
	while(R(id)){
		id = R(id);
		push_down(id);
	}
	return id;
}
int getMin(int id){
	push_down(id);
	while(L(id)){
		id = L(id);
		push_down(id);
	}
	return id;
}

void Print(ll id){
	push_down(id);
	if(L(id))Print(L(id));
	if(id != 1 && id != 2)printf("%lld\n",tree[id].num);
	if(R(id))Print(R(id));
}

ll n;
void init(){
	tot = 0; root = 0;
	Father(0) = L(0) = R(0) = tree[0].size = 0;
	tree[0].num = -1;
	Newnode(root, 0, -1);
	Newnode(R(root), root, -1);

	build(1,n,L(R(root)),R(root));
	push_up(R(root));	push_up(root);
}

int main(){
	ll que, u, v;
	while(~scanf("%lld %lld",&n,&que)){
		init();
		while(que--){
			scanf("%lld %lld", &u, &v);
			RotateTo(u, v);
			ll now = L(R(root));
			L(R(root)) = 0;
			push_up(R(root)); push_up(root);
			ll len = v-u+1;
			len = n - len +1;
			Splay(Get_kth(len),0);
			Splay(Get_kth(len-1), root);
			R(L(root)) = now;
			tree[now].fa = L(root);
			tree[now].filp ^= 1;
			push_up(L(root)); push_up(root);
		}
		Print(root);
	}
	return 0;
}
/*
10 2
2 5
4 8

题目链接：
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=40758#problem/E
*/

UVa 11922 Permutation Transformer splay 把序列翻转后放到结尾,布布扣,bubuko.com

UVa 11922 Permutation Transformer splay 把序列翻转后放到结尾

原文：http://blog.csdn.net/acmmmm/article/details/22061959