\(fhq-treap\) 实现.
我们旋转的时候已 \(r\) 用 \(size\) 分一次, 在左子树里用 \(l-1\) 再用 \(size\) 分一次, 剩下的右子树我们直接打个懒标记即可.
然后注意一下代码细节这题就做完了.
- My Code:
- #include <bits/stdc++.h>
- #define il inline
- #define temp template<class T>
- #define _swap(x,y) (x ^= y ^= x ^= y)
- const int MAXN = 1e5 + 10;
- using namespace std;
- temp il void rd(T& res) {
- res = 0;char c;bool sign = 0;
- for(c = getchar();!isdigit(c);c = getchar()) sign |= c == '-';
- for(;isdigit(c);c = getchar()) res = (res <<1) + (res << 3) + (c ^ 48);
- (sign) && (res = -res);
- return;
- }
- int n,m,i,j,k,cnt,root,q;
- struct TreeNode {
- int ch[2],val,size,rnd;
- bool rev;
- }tr[MAXN];
- il int NewNode(int v) {
- tr[++cnt].val = v;
- tr[cnt].size = 1;tr[cnt].rnd = rand();
- return cnt;
- }
- il void pushup(int o) {
- tr[o].size = tr[tr[o].ch[0]].size + tr[tr[o].ch[1]].size + 1;
- return;
- }
- il void pushdown(int o) {
- tr[o].rev ^= 1;
- _swap(tr[o].ch[0],tr[o].ch[1]);
- tr[tr[o].ch[0]].rev ^= 1;
- tr[tr[o].ch[1]].rev ^= 1;
- return;
- }
- int build(int l,int r) {
- if(l> r) return 0;
- int mid = l + r>> 1;
- int x = NewNode(mid);
- tr[x].ch[0] = build(l,mid - 1);
- tr[x].ch[1] = build(mid + 1,r);
- pushup(x);
- return x;
- }
- void split_k(int u,int k,int& x,int& y) {
- if(!u) {
- x = y = 0;
- return;
- }
- if(tr[u].rev) pushdown(u);
- if(k <= tr[tr[u].ch[0]].size) {
- y = u;
- split_k(tr[u].ch[0],k,x,tr[u].ch[0]);
- pushup(y);
- } else {
- x = u;
- split_k(tr[u].ch[1],k - tr[tr[u].ch[0]].size - 1,tr[u].ch[1],y);
- pushup(x);
- }
- }
- void print(int rt) {
- if(!rt) return;
- if(tr[rt].rev) pushdown(rt);
- if(tr[rt].ch[0]) print(tr[rt].ch[0]);
- printf("%d",tr[rt].val);
- if(tr[rt].ch[1]) print(tr[rt].ch[1]);
- return;
- }
- int merge(int u,int v) {
- if(!u) return v;if(!v) return u;
- if(tr[u].rev) pushdown(u);if(tr[v].rev) pushdown(v);
- if(tr[u].rnd < tr[v].rnd) {
- tr[u].ch[1] = merge(tr[u].ch[1],v);
- pushup(u);
- return u;
- } else {
- tr[v].ch[0] = merge(u,tr[v].ch[0]);
- pushup(v);
- return v;
- }
- }
- int main() {
- srand((unsigned)time(NULL));
- rd(n);rd(q);
- root = build(1,n);
- while(q--) {
- int l,r,a,b,c,d;rd(l);rd(r);
- split_k(root,r,a,b);
- split_k(a,l - 1,c,d);
- tr[d].rev ^= 1;
- root = merge(merge(c,d),b);
- }
- print(root);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2949982.html