3223: Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 2202 Solved: 1226
[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
【思路】
Splay Tree处理区间翻转。
分裂后打标记，然后合并即可。
【代码】
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int maxn = +;
struct Node{
Node* ch[];
int v,s,flip;
int cmp(int k) {
int d=k-ch[]->s;
if(d==) return -;
return d<=? :;
}
void maintain() {
s=ch[]->s+ch[]->s+;
}
void pushdown() {
if(flip) {
flip=;
swap(ch[],ch[]);
ch[]->flip^=;
ch[]->flip^=;
}
}
};
Node* null=new Node();
void rotate(Node* &o,int d) {
Node* k=o->ch[d^]; o->ch[d^]=k->ch[d]; k->ch[d]=o;
o->maintain(),k->maintain(); o=k;
}
void splay(Node* &o,int k) {
o->pushdown();
int d=o->cmp(k);
if(d==) k-=o->ch[]->s+;
if(d!=-) {
Node* p=o->ch[d];
p->pushdown();
int d2=p->cmp(k);
int k2=d2==? k:k-p->ch[]->s-;
if(d2!=-) {
splay(p->ch[d2],k2);
if(d==d2) rotate(o,d^); else rotate(o->ch[d],d);
}
rotate(o,d^);
}
}
Node* merge(Node* left,Node* right) {
splay(left,left->s);
left->ch[]=right,left->maintain();
return left;
}
void split(Node* o,int k,Node* &left,Node* &right) {
splay(o,k);
left=o,right=left->ch[],left->ch[]=null;
left->maintain();
}
struct SplaySequence {
int n;
Node seq[maxn];
Node* root; Node* build(int sz) {
if(!sz) return null;
Node* l=build(sz/);
Node* o=&seq[++n];
o->v=n;
o->ch[]=l;
o->ch[]=build(sz-sz/-);
o->flip=o->s=;
o->maintain();
return o;
}
void init(int sz) {
n=null->s=;
root=build(sz);
}
}spaly;
vector<int> ans;
void print(Node* o) {
if(o!=null) {
o->pushdown();
print(o->ch[]);
ans.push_back(o->v);
print(o->ch[]);
}
} int read() {
char c=getchar();
while(!isdigit(c)) c=getchar();
int x=;
while(isdigit(c)) {
x=x*+c-'';
c=getchar();
}
return x;
}
int n,m;
int main() {
n=read(),m=read();
spaly.init(n+); //在开始添加虚拟结点
int l,r;
Node *left,*right,*mid;
while(m--) {
l=read(),r=read();
split(spaly.root,l,left,right);
split(right,r-l+,mid,right);
mid->flip^=;
spaly.root = merge(merge(left,mid),right);
}
print(spaly.root);
for(int i=;i<ans.size();i++) printf("%d ",ans[i]-);
return ;
}