https://www.luogu.org/problem/show?pid=3391

乍一看上去根本无法下手，由于翻转会使元素的位置发生改变，故不能使用差分；而暴力又必然TLE。于是无耻地参（zhao）考（chao）了题解区神犇的思路……

题意

维护一个数据结构，支持区间翻转。

分析

【定理1】：二叉树的性质 将二叉树上某一棵子树上所有左右儿子交换，得到的新子树的中序遍历恰与原子树中序遍历相反。

证：用归纳法，设子树规模为k 1. 若 k=1 ，显然成立 2. 若 k>1 ，设根为 nr ，子树的中序遍历为 n1,n2,n3,...,nr−1,nr,nr+1,...,nk ，若对于左右子树均成立，（原）左子树的中序遍历变为： nr−1,nr−2,...,n1 ，（原）右子树的中序遍历变为： nk,nk−1,...,nr+1 ，将左右子树交换，变为： nk,nk−1,nk−2,...,nr+1,nr,nr−1,...n1 ，要求成立。根据归纳原理，原命题得证。

【定理2】：二叉树上区间旋转性质 设二叉树上有两个元素k, p(中序遍历中k在p左侧)，利用Treap旋转将k旋到根，p旋到k的右孩子，则p的左子树恰为原中序遍历中k, p之间的所有元素。

证：由于Treap旋转不改变中序遍历，该结论显然。

基于以上两个定理可以得出以下算法： 1. 用0..n+1序列建一棵二叉排序树（ Θ(nlgn) ）； 2. 对于任何一个询问l, r，找到二叉树中序遍历中为l-1，r+1的两个元素记为p, q（期望 Θ(lgn) ）； 3. 先把q旋转到根，再把p旋转到根（由于p在q的左面，这时，p必然是根，q必然是根的右孩子）（期望 Θ(lgn) ）； 4. 将q的左子树上所有节点的左右孩子交换（用Lazy_Tag，摊还 Θ(1) ）； 5. 最后中序遍历输出 [1,n] 中所有元素即可

代码

代码又丑又长，将就着看吧…

#include <bits/stdc++.h> using namespace std; struct node { int lc, rc, fa; int dat; int label; int lsize, rsize; node() { lsize = rsize = label = fa = lc = rc = dat = 0; dat = -1; } inline int size() { if (dat == -1) return 0; return lsize + rsize + 1; } } tree[1000005]; int top = 0; int n, m; int root = 1; inline void push_label(int i) { if (tree[i].label) { swap(tree[i].lc, tree[i].rc); swap(tree[i].lsize, tree[i].rsize); tree[i].label = 0; tree[tree[i].lc].label ^= 1; tree[tree[i].rc].label ^= 1; } } int build_tree(int l, int r, int &nd) { if (l > r) return 0; if (l == r) { tree[nd].dat = l; return 1; } int mid = (l+r)>>1, ths = nd; tree[nd].dat = mid; tree[nd].lc = nd+1; tree[nd+1].fa = ths; tree[ths].lsize = build_tree(l, mid-1, ++nd); tree[ths].rc = nd+1; tree[nd+1].fa = ths; tree[ths].rsize = build_tree(mid+1, r, ++nd); return tree[ths].lsize + tree[ths].rsize + 1; } void dfs(int i, int tab = 0) // for debugging { if (i == 0) return; push_label(i); for (int i = 1; i <= tab; i++) putchar(' '); cout << tree[i].dat << '(' << tree[i].lsize << ',' << tree[i].rsize << ',' << tree[tree[i].fa].dat << ')' << endl; dfs(tree[i].lc, tab+2); dfs(tree[i].rc, tab+2); } void print(int i) { if (i == 0) return; push_label(i); print(tree[i].lc); if (tree[i].dat >= 1 && tree[i].dat <= n) printf("%d ", tree[i].dat); print(tree[i].rc); } inline void lift_left_up(int i) { if (i == root) root = tree[i].lc; push_label(i); int pos = tree[i].lc; tree[i].lc = tree[pos].rc; tree[tree[pos].rc].fa = i; tree[pos].rc = i; tree[pos].fa = tree[i].fa; tree[i].fa = pos; if (tree[tree[pos].fa].rc == i) tree[tree[pos].fa].rc = pos; else tree[tree[pos].fa].lc = pos; tree[i].lsize = tree[tree[i].lc].size(); tree[pos].rsize = tree[tree[pos].rc].size(); //cout << tree[i].dat << " Lift Left Up Get : \n"; //dfs(root); } inline void lift_right_up(int i) { if (i == root) root = tree[i].rc; push_label(i); int pos = tree[i].rc; tree[i].rc = tree[pos].lc; tree[tree[pos].lc].fa = i; tree[pos].lc = i; tree[pos].fa = tree[i].fa; tree[i].fa = pos; if (tree[tree[pos].fa].rc == i) tree[tree[pos].fa].rc = pos; else tree[tree[pos].fa].lc = pos; tree[i].rsize = tree[tree[i].rc].size(); tree[pos].lsize = tree[tree[pos].lc].size(); //cout << tree[i].dat << " Lift Right Up Get : \n"; //dfs(root); } inline void lift_up(int i) { push_label(i); if (i == tree[tree[i].fa].lc) lift_left_up(tree[i].fa); else lift_right_up(tree[i].fa); } int find_kth(int i, int k) // from i, find the first element with k pre_element { push_label(i); if (tree[i].lsize == k) return i; if (tree[i].lsize > k) return find_kth(tree[i].lc, k); else return find_kth(tree[i].rc, k-tree[i].lsize-1); } void lift(int l, int r) { l = find_kth(root, l-1); r = find_kth(root, r+1); //cout << tree[l].dat << " " << tree[r].dat << endl; while (r != root) lift_up(r); while (l != root) lift_up(l); tree[tree[r].lc].label ^= 1; //cout << "Successfully dealed " << l << " , " << r << endl; } int main() { scanf("%d%d", &n, &m); build_tree(0, n+1, ++top); int l, r; for (int i = 1; i <= m; i++) { scanf("%d%d", &l, &r); lift(l, r); } print(root); return 0; }

总结

这个题说实话要不是题目提示根本想不到用树……建(二声)模(轻声)思(三声)想(三声)及其(连读加快)诡(四声)异(二声)，代(二声)码(轻声)量(二声)极大(连读加重,三声、二声)。【强行Orz物理老师】

将交换左右子树的操作改变可以开发出其他功能，例如区间修改、找区间k大和区间求和（貌似代替了许多树套树的操作？）。区间问题又多了一个武器2333……