bzoj1861 书架
程序员文章站
2022-07-10 23:41:18
题目链接 思路 用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。 操作1,就把x从平衡树中删掉,然后将其权值变为最小值,重新插入。 操作2,与操作1类似,只要将其权值变为最大值再重新插入就行了。 操作3,其实就是将x与他的前驱或者后继交换。也很容易实现。 操作4,查询排名。 操作5,查找第 ......
思路
用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。
操作1,就把x从平衡树中删掉,然后将其权值变为最小值,重新插入。
操作2,与操作1类似,只要将其权值变为最大值再重新插入就行了。
操作3,其实就是将x与他的前驱或者后继交换。也很容易实现。
操作4,查询排名。
操作5,查找第k大。
代码
/* * @author: wxyww * @date: 2019-05-25 10:50:13 * @last modified time: 2019-05-25 17:21:41 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; #define ls tr[cur].ch[0] #define rs tr[cur].ch[1] const int n = 500000 + 100,inf = 1e9 + 10; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int ch[2],val,id,key,siz; }tr[n]; int tot; int root,dy[n]; void up(int cur) { tr[cur].siz = tr[ls].siz + tr[rs].siz + 1; } void rotate(int &cur,int f) { int son = tr[cur].ch[f]; tr[cur].ch[f] = tr[son].ch[f ^ 1]; tr[son].ch[f ^ 1] = cur; up(cur); cur = son; up(cur); } void insert(int &cur,int val,int key) { if(!cur) { cur = ++tot; tr[cur].val = val;tr[cur].key = key; tr[cur].id = rand();tr[cur].siz = 1; dy[key] = cur; return; } tr[cur].siz++; int d = val > tr[cur].val; insert(tr[cur].ch[d],val,key); if(tr[tr[cur].ch[d]].id < tr[cur].id) rotate(cur,d); } void del(int &cur,int val) { if(!cur) return; if(val == tr[cur].val) { if(!ls || !rs) {cur = ls + rs;return;} int d = tr[rs].id < tr[ls].id;rotate(cur,d); del(cur,val); } else tr[cur].siz--,del(tr[cur].ch[val > tr[cur].val],val); } int rank(int cur,int val) { if(!cur) return 0; if(val == tr[cur].val) return tr[ls].siz; if(val < tr[cur].val) return rank(ls,val); else return rank(rs,val) + tr[ls].siz + 1; } int kth(int cur,int now) { while(1) { if(tr[ls].siz >= now) cur = ls; else if(tr[ls].siz + 1 == now) return tr[cur].key; else now -= tr[ls].siz + 1,cur = rs; } } int pred(int cur,int val) { if(!cur) { tr[++tot].val = -inf; return tot; } if(val <= tr[cur].val) return pred(ls,val); int k = pred(rs,val); return tr[k].val > tr[cur].val ? k : cur; } int nex(int cur,int val) { if(!cur) { tr[++tot].val = inf; return tot; } if(val >= tr[cur].val) return nex(rs,val); int k = nex(ls,val); return tr[k].val < tr[cur].val ? k : cur; } int ll,rr,a[n]; char s[10]; int main() { srand(time(0)); int n = read(),m = read(); for(int i = 1;i <= n;++i) { int x = read(); a[x] = i,insert(root,++rr,x); } while(m--) { scanf("%s",s + 1); if(s[1] == 't') { int x = read(); del(root,a[x]); a[x] = --ll; insert(root,ll,x); } else if(s[1] == 'b') { int x = read(); del(root,a[x]);a[x] = ++rr; insert(root,rr,x); } else if(s[1] == 'i') { int x = read(),y = read(); if(!y) continue; int tmp; if(y == -1) tmp = pred(root,a[x]); else tmp = nex(root,a[x]); int zz = tr[tmp].key; swap(tr[tmp].key,tr[dy[x]].key); // printf("!!%d %d\n",x,zz); swap(dy[x],dy[zz]); swap(a[x],a[zz]); } else if(s[1] == 'a') { int x = read(); printf("%d\n",rank(root,a[x])); } else { int x = read(); printf("%d\n",kth(root,x)); } } return 0; }