莞中 2022暑假训练题02：平衡树

本文代码全部使用 FHQ-Treap, 不了解 FHQ-treap 的可以参考 我的博客。

T1 普通平衡树

板子题，参考上面的博客。

#include 
using namespace std;const int N = 1e5 + 10;struct Node
{int l,r;int val;// real valueint key;// for treapint size;
}fhq[N];
int root,cnt;mt19937 rnd(233);int create(int val)
{fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;return cnt;
}void pushup(int u)
{fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}void split(int u,int val,int &x,int &y)
{if(!u) {x = y = 0;return;}if(fhq[u].val <= val){x = u;split(fhq[u].r,val,fhq[u].r, y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y)
{if(!x || !y) return x + y;if(fhq[x].key >= fhq[y].key){fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}int x,y,z;
void insert(int val)
{split(root,val,x,y);root = merge(merge(x,create(val)), y);
}void del(int val)
{split(root,val,x,z);split(x,val-1,x,y);y = merge(fhq[y].l,fhq[y].r);root = merge(merge(x,y),z);
}void getrank(int val)
{split(root,val-1,x,y);printf("%d\n",fhq[x].size);root = merge(x,y);
}void getval(int rank)	
{rank++;int u = root;while(u){if(fhq[fhq[u].l].size + 1 == rank) break;if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;}printf("%d\n", fhq[u].val);
}void pre(int val)
{split(root,val-1,x,y);int u = x;while(fhq[u].r) u = fhq[u].r;printf("%d\n",fhq[u].val);root = merge(x,y);
}void nxt(int val)
{split(root,val,x,y);int u = y;while(fhq[u].l) u = fhq[u].l;printf("%d\n",fhq[u].val);root = merge(x,y);
}int main()
{int n;scanf("%d",&n);insert(2147483647), insert(-2147483647);while(n--){int opt,val;scanf("%d%d",&opt,&val);if(opt == 1) insert(val);if(opt == 2) del(val);if(opt == 3) getrank(val);if(opt == 4) getval(val);if(opt == 5) pre(val);if(opt == 6) nxt(val);}return 0;
}

T2 宠物收养所

####【题意】
有一个宠物收容所，宠物和人都有一个值，人来了就会拿走一只和他的值最接近的宠物。

####【思路】(按值建立FHQ-treap)
存一下当前是宠物多还是顾客多，随时在宠物和顾客之间转换。

每一次加进来一个宠物时，如果是宠物树就直接插入，否则查找当前顾客的期望的前驱和后继（不是严格的），拉出来删除，统计答案，反之如果是顾客树，就反着来做就行了。

#include 
using namespace std;typedef long long LL;const LL N = 80005, Mod = 1000000;struct Node
{int l,r;LL val,key;LL size;
}fhq[N];
int root,cnt;
int kind; // ¨º¡Â¨¤?¡Á¡ã¦Ì?¨º?¨¨??1¨º?1¡¤ 
int n;
int x,y,z;void pushup(int u)
{fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}void split(int u,LL val,int &x,int &y)
{if(!u) {x = y = 0;return ;}if(fhq[u].val <= val) {x = u;split(fhq[u].r,val,fhq[u].r,y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y)
{if(!x || !y) return x | y;if(fhq[x].key >= fhq[y].key){fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else{fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}mt19937 rnd(233);
int intree = 0;
int create(LL val)
{fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;return cnt;
}void insert(LL val)
{split(root,val,x,y);root = merge(merge(x,create(val)),y);
}void del(LL val)
{
//	intree --;split(root,val,x,z);split(x,val-1,x,y);y = merge(fhq[y].l,fhq[y].r);root = merge(x,merge(y,z));
//	cnt --;
}LL pre(LL val)
{split(root,val-1,x,y);int u = x;while(fhq[u].r) u = fhq[u].r;LL res = fhq[u].val;root = merge(x,y);return res;
}LL nxt(LL val)
{split(root,val,x,y);int u = y;while(fhq[u].l) u = fhq[u].l;LL res = fhq[u].val;root = merge(x,y);return res;
}int main()
{
//	freopen("input.txt","r",stdin);scanf("%d",&n);insert(-1e10),insert(1e10);long long ans = 0;while(n --){LL opt, val;scanf("%lld%lld",&opt,&val);if(!intree || opt == kind){intree ++;insert(val);kind = opt;}else{			intree --;LL val1 = pre(val);			LL val2 = nxt(val);if(abs(val-val1) < abs(val-val2)) del(val1),ans = (ans + abs(val-val1)) % Mod;else del(val2),ans = (ans + abs(val-val2)) % Mod;}}	printf("%lld",ans);return 0;
}

T3 郁闷的出纳员

####【题意】
有一些询问，每一次询问可以加入一个员工，给所有员工加工资和减工资，查询第k大的工资是多少。
减工资时可能会使得一些员工的工资小于一个工资下限 $minn$，那他们就会离开公司。

####【思路】(按值建立FHQ-treap)
维护一个变量 $delta$,表示集体加了多少工资和减了多少工资。
加入员工时要将员工的初始工资减去 $delta$，再插入到平衡树中。
加工资的时候就更新一下 $delta$ 即可。
减工资的时候要更新 $delta$，并将小于 $minn-delta$ 的员工删掉。

#include 
using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;struct Node
{int l,r;int val;// real valueint key;// for treapint siz;
}fhq[N];
int root,cnt;mt19937 rnd(233);int create(int val)
{fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].siz = 1;return cnt;
}void pushup(int u)
{fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}void split(int u,int val,int &x,int &y)
{if(!u) {x = y = 0;return;}if(fhq[u].val <= val){x = u;split(fhq[u].r,val,fhq[u].r, y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y) 
{if(!x || !y) return x + y;if(fhq[x].key >= fhq[y].key){fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}int x,y,z;
void insert(int val)
{split(root,val,x,y);root = merge(merge(x,create(val)), y);
}void del(int val)
{split(root,val,x,z);	split(x,val-1,x,y);y = merge(fhq[y].l,fhq[y].r);root = merge(merge(x,y),z);
}void getrank(int val)
{split(root,val-1,x,y);printf("%d\n",fhq[x].siz);root = merge(x,y);
}int getval(int rank)	
{int u = root;while(u){if(fhq[fhq[u].l].siz + 1 == rank) break;if(fhq[fhq[u].l].siz >= rank) u = fhq[u].l;else rank -= fhq[fhq[u].l].siz + 1, u = fhq[u].r;}return fhq[u].val;
}void pre(int val)
{split(root,val-1,x,y);int u = x;while(fhq[u].r) u = fhq[u].r;printf("%d\n",fhq[u].val);root = merge(x,y);
}void nxt(int val)
{split(root,val,x,y);int u = y;while(fhq[u].l) u = fhq[u].l;printf("%d\n",fhq[u].val);root = merge(x,y);
}int main()
{int n, minn;scanf("%d%d",&n,&minn);int x,delta=0,leave=0;while(n --){char opt[2];scanf("%s%d",opt,&x);if(opt[0] == 'I' && x >= minn) insert(x - delta);else if(opt[0] == 'A') delta += x;else if(opt[0] == 'S'){delta -= x;split(root,minn - delta - 1,x,y);leave += fhq[x].siz;root = y;}else if(opt[0] == 'F'){if(fhq[root].siz < x) puts("-1");else printf("%d\n",getval(fhq[root].siz-x+1)+delta);}}printf("%d\n",leave);return 0;
}

T4 营业额统计

【题意】

给出一个长为 $n$ 的序列 $a$， 定义 f i = m i n { ∣ a i − a j ∣ } ( 1 ≤ j < i ≤ n ) f_i = min\{ |a_i - a_j| \}\; (1 \le j < i \le n) fi​=min{∣ai​−aj​∣}(1≤j<i≤n)。
求 ∑ f i \sum f_i ∑fi​。

【思路】(按值建立FHQ-treap)

依次插入 a i a_i ai​，插入后查找 a i a_i ai​ 的前驱和后继，取它们减去 a i a_i ai​ 的绝对值的较小值。

#include 
using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;struct Node
{int l,r;int val;// real valueint key;// for treapint size;
}fhq[N];
int root,cnt;mt19937 rnd(233);int create(int val)
{fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].size = 1;return cnt;
}void pushup(int u)
{fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}void split(int u,int val,int &x,int &y)
{if(!u) {x = y = 0;return;}if(fhq[u].val <= val){x = u;split(fhq[u].r,val,fhq[u].r, y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y) // ±??¤x?Dµ?è?òa?a??µ?val??±èy?Dµ?è?òa?a??D? 
{if(!x || !y) return x + y;if(fhq[x].key >= fhq[y].key){fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}int x,y,z;
void insert(int val)
{split(root,val,x,y);root = merge(merge(x,create(val)), y);
}void del(int val)
{split(root,val,x,z);	split(x,val-1,x,y);y = merge(fhq[y].l,fhq[y].r);root = merge(merge(x,y),z);
}void getrank(int val)
{split(root,val-1,x,y);printf("%d\n",fhq[x].size);root = merge(x,y);
}void getval(int rank)	
{rank++;int u = root;while(u){if(fhq[fhq[u].l].size + 1 == rank) break;if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;}printf("%d\n", fhq[u].val);
}int pre(int val)
{split(root,val-1,x,y);int u = x;while(fhq[u].r) u = fhq[u].r;int ans = fhq[u].val;root = merge(x,y);return ans;
}int nxt(int val)
{split(root,val,x,y);int u = y;while(fhq[u].l) u = fhq[u].l;int ans = fhq[u].val;root = merge(x,y);return ans;
}unordered_map<int,int> h;int main()
{int n;scanf("%d",&n);insert(INF), insert(-INF);int ans = 0, x;for(int i=1;i<=n;i++){scanf("%d",&x);h[x] ++;insert(x);if(i == 1) ans += x;else if(h[x] <= 1) ans += min(abs(x - pre(x)), abs(x - nxt(x)));}cout<<ans;return 0;
}

T5 Double Queue

【题意】

有若干次操作，每次操作可以将一个人 $k$，按优先级 $p$ 插入一条等待队列中，可以询问队列中的最大（或最小）优先级的人，并将其从队列中删除。
保证所有的 $k$ 和所有的 $p$ 互不相同。

【思路】(按值建立FHQ-treap)

建立一个 $k$ 和 $p$ 的映射关系。
先在平衡树中插入哨兵 $\text{-INF}$ 和 $\text{INF}$。
加入一个人的时候将其的 $p$ 插入平衡树中。
询问最大的时候就输出 $\text{INF}$ 的前驱对应的 $k$。
询问最小的时候就输出 $\text{-INF}$ 的后继对应的 $k$。

#include 
#include 
#include 
#include 
#include 
using namespace std;const int N = 1e5 + 10, INF = 0x3f3f3f3f;struct Node
{int l,r;int val;// real valueint key;// for treapint size;
}fhq[N];
int root,cnt;//mt19937 rand(233);int create(int val)
{fhq[++cnt].val = val,fhq[cnt].key = rand(),fhq[cnt].size = 1;return cnt;
}void pushup(int u)
{fhq[u].size = fhq[fhq[u].l].size + fhq[fhq[u].r].size + 1;
}void split(int u,int val,int &x,int &y)
{if(!u) {x = y = 0;return;}if(fhq[u].val <= val){x = u;split(fhq[u].r,val,fhq[u].r, y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y) 
{if(!x || !y) return x + y;if(fhq[x].key >= fhq[y].key){fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}int x,y,z;
void insert(int val)
{split(root,val,x,y);root = merge(merge(x,create(val)), y);
}void del(int val)
{split(root,val,x,z);	split(x,val-1,x,y);y = merge(fhq[y].l,fhq[y].r);root = merge(merge(x,y),z);
}void getrank(int val)
{split(root,val-1,x,y);printf("%d\n",fhq[x].size);root = merge(x,y);
}void getval(int rank)	
{rank++;int u = root;while(u){if(fhq[fhq[u].l].size + 1 == rank) break;if(fhq[fhq[u].l].size >= rank) u = fhq[u].l;else rank -= fhq[fhq[u].l].size + 1, u = fhq[u].r;}printf("%d\n", fhq[u].val);
}map<int,int> h;
int pre(int val)
{split(root,val-1,x,y);int u = x;while(fhq[u].r) u = fhq[u].r;int ans = fhq[u].val;	root = merge(x,y);return ans;
}int nxt(int val)
{split(root,val,x,y);int u = y;while(fhq[u].l) u = fhq[u].l;int ans = fhq[u].val;	root = merge(x,y);return ans;
}int main()
{srand(time(0));int opt;insert(-INF),insert(INF);while(~scanf("%d",&opt)){if(opt == 0) break;if(opt == 1){int k, p;scanf("%d%d",&k,&p);h[p] = k;insert(p);}if(opt == 2){int p = pre(INF);cout<<h[p]<<endl;del(p);}if(opt == 3){int p = nxt(-INF);cout<<h[p]<<endl;del(p);}}return 0;
}

T6 Buy Tickets

####【题意】
有 n ( 1 ≤ n ≤ 2 × 1 0 5 ) n (1 \le n \le 2\times 10^5) n(1≤n≤2×105) 个询问，每次询问将一个值 $val$ 插到 $pos$ 的后面。

【思路】(按下标建立FHQ-Treap)

明显需要一个 $O(n\log n)$ 的算法。

考虑使用按下标为关键字的 FHQ-Treap。

每次插入都将按 pos 来 Split。

再将整个树合并起来即可。

#include 
#include 
#include 
#include 
#include 
using namespace std;const int N = 300010;struct Node
{int l,r;int val;// real valueint key;// for treapint siz;int laz;
}fhq[N];
int root,cnt;int create(int val)
{fhq[++cnt].val = val,fhq[cnt].key = rand(),fhq[cnt].siz = 1;return cnt;
}void pushup(int u)
{fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}void pushdown(int u)
{swap(fhq[u].l,fhq[u].r);fhq[fhq[u].l].laz ^= 1;fhq[fhq[u].r].laz ^= 1;fhq[u].laz = 0;
}void split(int u,int val,int &x,int &y)
{if(!u) {x = y = 0;return;}if(fhq[u].laz) pushdown(u);if(fhq[fhq[u].l].siz+1 <= val){x = u;split(fhq[u].r,val-(fhq[fhq[u].l].siz+1),fhq[u].r, y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y)
{if(!x || !y) return x + y;if(fhq[x].key >= fhq[y].key){if(fhq[x].laz) pushdown(x);fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {if(fhq[y].laz) pushdown(y);fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}int x,y,z;
int n, m;	
void print(int u)
{if(fhq[u].laz) pushdown(u);if(fhq[u].l) print(fhq[u].l);printf("%d ",fhq[u].val);if(fhq[u].r) print(fhq[u].r);
}int main()
{while(~scanf("%d",&n)){srand(time(0));root = cnt = 0;memset(fhq,0,sizeof fhq);for(int i=1;i<=n;i++) {int pos,val;scanf("%d%d",&pos,&val);if(pos == 0) root = merge(create(val),root);else {split(root,pos,x,y);root = merge(merge(x,create(val)),y);}}print(root);cout<<endl;}return 0;
}

T7 I Hate It

####【题意】
维护区间最大值，单点修改。

####【思路】
板子线段树秒杀。

平衡树做法略显复杂。

询问最大值就查询 INF 的前驱即可。
单点修改就要删掉原来的值，再插入一个新的值。

赛时极限7分钟A掉这道题(doge

#include 
using namespace std;typedef long long LL;const int N = 2 * 1e5 + 10;struct Node
{int l,r;LL val;
}tr[N * 4];LL w[N];void pushup(int u)
{tr[u].val = max(tr[u<<1].val, tr[u<<1|1].val);
}void build(int u,int l,int r)
{if(l == r) tr[u] = Node{l,r,w[r]};else{tr[u].l = l,tr[u].r = r;int mid = l + r >> 1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}
}void modify(int u,int x,LL val)
{if(tr[u].l == x && tr[u].r == x) tr[u].val = max(tr[u].val,val);else{int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) modify(u<<1,x,val);if(x > mid) modify(u<<1|1,x,val);pushup(u);}
}LL query(int u,int l,int r)
{if(l <= tr[u].l && tr[u].r <= r) return tr[u].val;else{int mid = tr[u].l + tr[u].r >> 1;LL ans = -1e9;if(l <= mid) ans = max(ans,query(u<<1,l,r));if(r > mid) ans = max(ans,query(u<<1|1,l,r));return ans;}
}int main()
{int n,m;while(~scanf("%d%d",&n,&m)){for(int i=1;i<=n;i++) scanf("%lld",&w[i]);build(1,1,n);while(m --){char opt[3];LL x,y;scanf("%s%lld%lld",opt,&x,&y);if(opt[0] == 'U') modify(1,x,y);else cout << query(1,x,y) << endl;}}return 0;
}

T8 Robotic Sort

【题意】

给出一个序列，对于每一个 $i$，要求翻转一段连续区间，使得第 $i$ 小的数翻转到i的位置。

【思路】(按下标建立FHQ-Treap)

区间翻转可以使用 Splay 或者 FHQ-Treap。

本人擅长 FHQ-Treap，下面讲一下 FHQ-Treap 如何实现区间翻转。

假设现在要翻转区间 $[a,b]$。
首先我们要用两次 Split 将区间 $[a,b]$ 抠出来，一次按 b Split，一次按 a-1 Split。
之后我们要借助懒标记，标记这个区间需要翻转。
需要获取序列或输出序列的时候的时候需要中序遍历一遍树。
注意，所有需要懒标记的题目在递归前都需要 pushdown。(我在这里卡了好久)

对于这一题，首先要离散化一下数据，之后按下标建立 FHQ-Treap。

这题比较蛋疼的是，我们需要使用类似笛卡尔树的方式来建树，不然会被卡到 T 飞。

每一次都找到整棵树内的最小值，这个操作可以直接找 -INF 的后继，由于我们是使用类似笛卡尔树的建树方式，所以根结点就是最小值。

翻转过后，删掉最小值即可。

#include 
using namespace std;typedef long long LL;
const LL N = 100010;struct Node
{LL l,r;LL val;// real valueLL key;// for treapLL siz;LL laz;
}fhq[N];
LL root,cnt;mt19937 rnd(114514);LL create(LL val)
{fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].siz = 1;return cnt;
}void pushup(LL u)
{fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}void pushdown(LL u)
{swap(fhq[u].l,fhq[u].r);if(fhq[u].l) fhq[fhq[u].l].laz ^= 1;if(fhq[u].r) fhq[fhq[u].r].laz ^= 1;fhq[u].laz = 0;
}LL merge(LL x,LL y)
{if(!x || !y) return x + y;if(fhq[x].key < fhq[y].key){if(fhq[x].laz) pushdown(x);fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {if(fhq[y].laz) pushdown(y);fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}struct Point
{LL num,id;
} a[N];
LL b[N];bool cmp1(const Point& p,const Point& q) {return p.num < q.num;}
bool cmp2(const Point& p,const Point& q) {return p.id < q.id;}LL x,y,z;
LL n, m;int main()
{while(~scanf("%lld",&n)){if(n == 0) break;
//		scanf("%lld",&n);root = cnt = 0;memset(fhq,0,sizeof fhq);stack<LL> stk;for(LL i=1;i<=n;i++){scanf("%lld",&fhq[i].key);fhq[i].key = fhq[i].key * n + i;fhq[i].val = i, fhq[i].siz = 1;while(!stk.empty() && fhq[i].key < fhq[stk.top()].key) fhq[i].l = stk.top(), stk.pop(), pushup(fhq[i].l);if(!stk.empty()) fhq[stk.top()].r = i; stk.push(i);}while(!stk.empty()) root = stk.top(), pushup(stk.top()), stk.pop();for(LL i=1;i<=n;i++) {if(fhq[root].laz) pushdown(root);printf("%lld",fhq[fhq[root].l].siz+i);if(i < n) putchar(' ');fhq[fhq[root].l].laz ^= 1;LL l = fhq[root].l, r = fhq[root].r;fhq[root].l = fhq[root].r = 0;root = merge(l, r);}puts("");}return 0;
}

T9 Play with Chain

【题意】

有两种操作，一种是将区间 $[a,b]$ 取出，插到 $c$ 后面。
另一种是将区间 $[a,b]$ 翻转。

【思路】(按下标建立FHQ-Treap)

对于第一种操作，我们需要将按 b 和 a-1 Split两边，将区间 $[a,b]$ 抠出来，将原本的 $[a,b]$ 删掉，然后按 $c$ Split，最后将 $[a,b]$ 在 $c$ 之后合并起来。

对于第二种操作，可以参考本文T8 中的解释。

#include 
using namespace std;const int N = 300010;struct Node
{int l,r;int val;// real valueint key;// for treapint siz;int laz;
}fhq[N];
int root,cnt;mt19937 rnd(114514);int create(int val)
{fhq[++cnt].val = val,fhq[cnt].key = rnd(),fhq[cnt].siz = 1;return cnt;
}void pushup(int u)
{fhq[u].siz = fhq[fhq[u].l].siz + fhq[fhq[u].r].siz + 1;
}void pushdown(int u)
{swap(fhq[u].l,fhq[u].r);fhq[fhq[u].l].laz ^= 1;fhq[fhq[u].r].laz ^= 1;fhq[u].laz = 0;
}void split(int u,int val,int &x,int &y)
{if(!u) {x = y = 0;return;}if(fhq[u].laz) pushdown(u);if(fhq[fhq[u].l].siz+1 <= val){x = u;split(fhq[u].r,val-(fhq[fhq[u].l].siz+1),fhq[u].r, y);}else {y = u;split(fhq[u].l,val,x,fhq[u].l);}pushup(u);
}int merge(int x,int y)
{if(!x || !y) return x + y;if(fhq[x].key >= fhq[y].key){if(fhq[x].laz) pushdown(x);fhq[x].r = merge(fhq[x].r,y);pushup(x);return x;}else {if(fhq[y].laz) pushdown(y);fhq[y].l = merge(x,fhq[y].l);pushup(y);return y;}
}int x,y,z;
int n, m;	
int tot = 0;
void print(int u)
{if(fhq[u].laz) pushdown(u);if(fhq[u].l) print(fhq[u].l);printf("%d",fhq[u].val);tot++;if(tot <= n-1) putchar(' ');if(fhq[u].r) print(fhq[u].r);
}int main()
{while(~scanf("%d%d",&n,&m)){root = cnt = 0;memset(fhq,0,sizeof fhq);if(n == -1 && m == -1) break;for(int i=1;i<=n;i++) {create(i);root = merge(root,i);}while(m --){char opt[10];scanf("%s",opt);if(opt[0] == 'C'){int a,b,c;scanf("%d%d%d",&a,&b,&c);split(root,b,x,y);split(x,a-1,x,z);root = merge(x,y);split(root,c,x,y);root = merge(merge(x,z),y);}if(opt[0] == 'F'){int l, r;scanf("%d%d",&l,&r);split(root,r,x,y);split(x,l-1,x,z);fhq[z].laz^=1;root = merge(merge(x,z),y);} }		tot = 0;print(root);cout<<endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！