3223: Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 3884 Solved: 2235
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2……n-1,n) m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n
Output
输出一行n个数字，表示原始序列经过m次变换后的结果
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5
HINT
N,M<=100000
Source
不是特别难，打个lazy标记就行了，详见[Splay]
/**
* bzoj
* Problem#3223
* Accepted
* Time:2012ms
* Memory:4336k
*/
#include<iostream>
#include<fstream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef bool boolean;
#define smin(a, b) (a) = min((a), (b))
#define smax(a, b) (a) = max((a), (b))
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-' && x != -);
if(x == -) return;
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} template<typename T>
class SplayNode {
public:
T data;
int s;
boolean lazy;
SplayNode* next[];
SplayNode* father;
SplayNode():s(), lazy(){
memset(next, , sizeof(next));
}
SplayNode(T data, SplayNode* father):data(data), father(father), s(), lazy(){
memset(next, , sizeof(next));
}
int cmp(T a){
if(a == data) return -;
return (a > data) ? () : ();
}
int getWhich(SplayNode* p){
return (next[] == p) ? () : ();
}
void maintain(){
s = ;
for(int i = ; i < ; i++)
if(next[i] != NULL)
s += next[i]->s;
}
void pushDown(){
swap(next[], next[]);
for(int i = ; i < ; i++)
if(next[i] != NULL)
next[i]->lazy ^= ;
lazy = false;
}
}; template<typename T>
class Splay {
protected:
inline static void rotate(SplayNode<T>*& node, int d){
SplayNode<T> *father = node->father;
SplayNode<T> *newRoot = node->next[d ^ ];
if(newRoot->lazy) newRoot->pushDown();
node->next[d ^ ] = newRoot->next[d];
node->father = newRoot;
newRoot->next[d] = node;
newRoot->father = father;
if(node->next[d ^ ] != NULL) node->next[d ^ ]->father = node;
if(father != NULL) father->next[father->getWhich(node)] = newRoot;
node->maintain();
node->father->maintain();
} static SplayNode<T>* insert(SplayNode<T>*& node, SplayNode<T>* father, T data){
if(node == NULL){
node = new SplayNode<T>(data, father);
return node;
}
int d = node->cmp(data);
if(d == -) return NULL;
SplayNode<T>* res = insert(node->next[d], node, data);
if(res != NULL) node->maintain();
return res;
} static SplayNode<T>* findKth(SplayNode<T>*& node, int k){
if(node->lazy) node->pushDown();
int ls = (node->next[] != NULL) ? (node->next[]->s) : ();
if(k >= ls + && k <= ls + ) return node;
if(k <= ls) return findKth(node->next[], k);
return findKth(node->next[], k - ls - );
} public:
SplayNode<T> *root; Splay(){ } inline void splay(SplayNode<T>* node, SplayNode<T>* father){
if(node == father) return;
while(node->father != father){
SplayNode<T>* f = node->father;
int fd = f->getWhich(node);
SplayNode<T>* ff = f->father;
if(ff == father){
rotate(f, fd ^ );
break;
}
int ffd = ff->getWhich(f);;
if(ffd == fd){
rotate(ff, ffd ^ );
rotate(f, fd ^ );
}else{
rotate(f, fd ^ );
rotate(ff, ffd ^ );
}
}
if(father == NULL)
root = node;
} inline SplayNode<T>* insert(T data){
SplayNode<T>* res = insert(root, NULL, data);
if(res != NULL) splay(res, NULL);
return res;
} inline SplayNode<T>* findKth(int k, SplayNode<T>* father){
if(k <= || k > root->s) return NULL;
SplayNode<T>* p = findKth(root, k);
splay(p, father);
return p;
} SplayNode<T>* split(int from, int end){
if(from > end) return NULL;
if(from == && end == root->s){
findKth(, NULL);
return this->root;
}
if(from == ){
findKth(end + , NULL);
findKth(from, root);
return root->next[];
}
if(end == root->s){
findKth(from - , NULL);
findKth(end, root);
return root->next[];
}
findKth(end + , NULL);
findKth(from - , root);
return root->next[]->next[];
} void out(SplayNode<T>* node){
if(node == NULL) return;
if(node->lazy) node->pushDown();
out(node->next[]);
printf("%d ", node->data);
out(node->next[]);
} void debugOut(SplayNode<T>* node){ //调试使用函数，打印Splay
if(node == NULL) return;
cout << node->data << "(" << node->s << "," << ((node->father == NULL) ? (-) : (node->father->data)) << "," << node->lazy << "){";
debugOut(node->next[]);
cout << ",";
debugOut(node->next[]);
cout << "}";
}
}; int n, m;
Splay<int> s; int main(){
readInteger(n);
readInteger(m);
for(int i = ; i <= n; i++){
s.insert(i);
}
for(int i = , a, b; i<= m; i++){
readInteger(a);
readInteger(b);
if(a == b) continue;
SplayNode<int>* p = s.split(a, b);
p->lazy ^= ;
}
s.out(s.root);
return ;
}