文艺平衡树就是splay,维护区间反转,就是把所有左变成右,打个标记就好啦.一开始智障判断是否为根节点的时候傻乎乎的判断是否等于0...删了就好啦!
题干:
题目描述 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1 输入输出格式 输入格式： 第一行为n,m n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) (1,2, cdots n-1,n)(1,2,⋯n−1,n) m表示翻转操作次数 接下来m行每行两个数 [l,r][l,r][l,r] 数据保证 1≤l≤r≤n 1 leq l leq r leq n 1≤l≤r≤n 输出格式： 输出一行n个数字，表示原始序列经过m次变换后的结果
代码:
#include<iostream> #include<cstdio> #include<cmath> #include<ctime> #include<queue> #include<algorithm> #include<cstring> #define B cout << "Breakpoint!" << endl; #define O(a) cout << #a << " " << a << endl; using namespace std; #define duke(i,a,n) for(register int i = a;i <= n;i++) #define lv(i,a,n) for(register int i = a;i >= n;i--) #define clean(a) memset(a,0,sizeof(a)) const int INF = 1 << 30; typedef long long ll; typedef double db; template <class T> void read(T &x) { char c; bool op = 0; while(c = getchar(), c < '0' || c > '9') if(c == '-') op = 1; x = c - '0'; while(c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; if(op) x = -x; } int N,M,tot = 0; int root = 0; struct node { int ch[2],f,v; int siz,mark; void init(int x,int fa) { f = ch[0] = ch[1] = 0; siz = 1;v = x; f = fa; } }e[200010]; //#define root e[1].ch[1] inline void update(int x) { e[x].siz = e[e[x].ch[0]].siz + e[e[x].ch[1]].siz + 1; } inline void pushdown(int x) { if(e[x].mark) { e[e[x].ch[0]].mark ^= 1; e[e[x].ch[1]].mark ^= 1; e[x].mark = 0; swap(e[x].ch[0],e[x].ch[1]); } } inline int iden(int x) { return e[e[x].f].ch[0] == x ? 0 : 1; } inline void connect(int x,int f,int son) { e[x].f = f; e[f].ch[son] = x; } inline void rotate(int x) { int y = e[x].f; int mroot = e[y].f; int mrootson = iden(y); int yson = iden(x); int b = e[x].ch[yson ^ 1]; connect(b,y,yson); connect(y,x,yson ^ 1); connect(x,mroot,mrootson); update(y); update(x); } /*inline void splay(int at,int to) { while(e[at].f != to) { // O(e[at].f); // O(to); int y = e[at].f; int z = e[to].f; cout<<y<<" "<<z<<endl; if(z != to) rotate(at); else rotate(to); rotate(at); } if(to == 0) root = at; cout<<root<<endl; }*/ inline void splay(int at,int to) { while(e[at].f != to) { int up = e[at].f; if(e[up].f == to) rotate(at); else if(iden(up) == iden(at)) { rotate(up); rotate(at); } else { rotate(at); rotate(at); } } if(to == 0) root = at; // cout<<root<<endl; } inline void insert(int x) { int u = root,ff = 0; while(u) { ff = u; u = e[u].ch[x > e[u].v]; } u = ++tot; // cout<<x<<" "<<ff<<endl; if(ff) e[ff].ch[x > e[ff].v] = u; e[u].init(x,ff); splay(u,0); } inline int kth(int k) { int u = root; // cout<<"!!!"<<u<<endl; while(1) { pushdown(u); if(e[e[u].ch[0]].siz >= k) u = e[u].ch[0]; else if(e[e[u].ch[0]].siz + 1 == k) { // cout<<u<<endl; return u; } else { k -= e[e[u].ch[0]].siz + 1; u = e[u].ch[1]; } } } void write(int u) { pushdown(u); if(e[u].ch[0]) write(e[u].ch[0]); if(e[u].v > 1 && e[u].v < N + 2) printf("%d ",e[u].v - 1); if(e[u].ch[1]) write(e[u].ch[1]); } inline void work(int l,int r) { l = kth(l); r = kth(r + 2); splay(l,0); splay(r,l); e[e[e[root].ch[1]].ch[0]].mark ^= 1; } int main() { // freopen("in.in","r",stdin); read(N);read(M); duke(i,1,N + 2) insert(i); /*duke(i,1,N + 2) { printf("%d %d %d ",e[i].ch[0],e[i].ch[1],e[i].v); }*/ while(M--) { int l,r; read(l);read(r); work(l,r); /*duke(i,1,N + 2) { printf("%d %d %d ",e[i].ch[0],e[i].ch[1],e[i].v); }*/ } /*puts(""); duke(i,1,N + 2) { printf("%d %d %d ",e[i].ch[0],e[i].ch[1],e[i].v); }*/ write(root); puts(""); return 0; }