题目大意
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 。
题解
splay裸题，维护子树翻转信息即可。
代码:
#include <cstdio>#include <iostream>using namespace std;struct Node {int key,siz;bool flip;Node *ch[2],*fa;Node();Node(int);void pushdown();void maintain();int dir(int val) {if(val==ch[0]->siz+1) return -1;return val>ch[0]->siz+1;}int son() {if(fa->ch[1]==this) return 1;if(fa->ch[0]==this) return 0;return -1;}}*null,*root;Node:: Node():key(-1) {siz=null?1:0;flip=false;ch[0]=ch[1]=fa=null;}Node:: Node(int _):key(_) {siz=null?1:0;flip=false;ch[0]=ch[1]=fa=null;}void Node:: maintain() {siz=ch[0]->siz+1+ch[1]->siz;return;}void Node:: pushdown() {if(flip) {swap(ch[0],ch[1]);ch[0]->flip^=1, ch[1]->flip^=1;flip=false;}return;}void print(Node* cur) {if(cur==null) return;cur->pushdown();print(cur->ch[0]);cout<<cur->key<<" ";print(cur->ch[1]);}#define mid ((l+r)>>1)void build(Node* &cur,int l,int r) {if(l>r) {cur=null; return;}cur=new Node(mid);build(cur->ch[0],l,mid-1); cur->ch[0]->fa=cur;build(cur->ch[1],mid+1,r); cur->ch[1]->fa=cur;cur->maintain();}#undef midvoid Rotate(Node* cur,int dir) {Node* tmp=cur->ch[dir^1];cur->ch[dir^1]=tmp->ch[dir], tmp->ch[dir]->fa=cur;tmp->ch[dir]=cur;cur->maintain(), tmp->maintain();if(~cur->son()) cur->fa->ch[cur->son()]=tmp;tmp->fa=cur->fa, cur->fa=tmp;}void Pushdown(Node* cur) {if(cur->fa!=null) Pushdown(cur->fa);cur->pushdown();}void Splay(Node* cur) {while(~cur->son()) {int dir=cur->son();if(dir==cur->fa->son()) Rotate(cur->fa->fa,dir^1);Rotate(cur->fa,dir^1);}}Node* _find(Node *cur,int k) {cur->pushdown();int dir=cur->dir(k);if(dir==1) k-=cur->ch[0]->siz+1;if(dir==-1) return cur;else return _find(cur->ch[dir],k);}Node* Merge(Node *lhs,Node* rhs) {if(lhs==null) return rhs;if(rhs==null) return lhs;Node* tmp=_find(lhs,lhs->siz);Splay(tmp);tmp->ch[1]=rhs, rhs->fa=tmp, tmp->maintain();return tmp;}void Split(Node* org,int k,Node* &lhs,Node* &rhs) {if(k==0) {lhs=null, rhs=org;return;} else if(k==org->siz) {lhs=org, rhs=null;return;}Node* tmp=_find(org,k);Splay(tmp);lhs=tmp, rhs=tmp->ch[1];rhs->fa=null, lhs->ch[1]=null, lhs->maintain();return;}void Reverse(int l,int r) {Node *lhs,*tmp,*mid,*rhs;Split(root,l-1,lhs,mid);Split(mid,r-l+1,mid,rhs);mid->flip^=1;root=Merge(Merge(lhs,mid),rhs);return;}int main() {#ifndef ONLINE_JUDGEfreopen("input.txt","r",stdin);freopen("output.txt","w",stdout);#endif // ONLINE_JUDGEnull=new Node();null->ch[0]=null->ch[1]=null->fa=null;root=null;int n,m;scanf("%d%d",&n,&m);build(root,1,n);for(int i=1;i<=m;i++) {int l,r;scanf("%d%d",&l,&r);Reverse(l,r);}print(root);return 0;}
