[luogu2596]:[ZJOI2006]书架

[luogu2596]:[ZJOI2006]书架

题目链接

我就是力量的化身


Solution

平衡树上维护每一个节点的,节点是书的优先级平衡的(初始时为1~n)

然后每一个节点上挂一个权值idx,表示这个节点所代表的书的编号

然后数组a[x]表示编号为x的书的优先级是多少

1 操作,我们将这个书的优先级变为当前最小优先级减一

2 操作,同上

3 操作,交换两个书的优先级

4 操作,直接查询a[x]的排名 – 1

5 操作 好像和平常的kth没有区别

FHQtrap 不知比我写的 splay 优越到哪里去了, dhy真是太强了,2分钟切掉(我还没读完题Orz)

QAQ


Code


\#include<cstdio> #include<cctype> #include<cstring> #include<ctime> #include<cstdlib> #include<algorithm> using namespace std; inline int read() { char c = getchar(); int x = 0, f = 1; while(!isdigit(c)) {if(c == '-') f = -1; c = getchar();} do {x = x * 10 + (c ^ 48); c = getchar();} while(isdigit(c)); return x * f; } const int N = 5e5 + 29; struct Node { int siz, rnd, val, idx; // val is prio and idx is true id Node *ch[2]; void maintain() { siz = 1 + ch[0]->siz + ch[1]->siz; } }; Node pool[N], *null, *root, *x, *y, *z, *r; int curminv, curmaxv, n, m; int a[N], qwq[N]; char c[233]; void init() { null = &pool[0]; null->siz = null->rnd = null->val = null->idx = 0; null->ch[0] = null->ch[1] = NULL; root = null; curminv = 1; curmaxv = n; } Node *newNode(int id, int p) { static int cnt = 1; pool[cnt].siz = 1; pool[cnt].rnd = rand(); pool[cnt].val = p; pool[cnt].idx = id; pool[cnt].ch[0] = pool[cnt].ch[1] = null; return &pool[cnt++]; } void split(Node *o, int k, Node *&x, Node *&y) { if(o == null) x = y = null; else { if(o->val <= k) { x = o; split(x->ch[1], k, x->ch[1], y); } else { y = o; split(y->ch[0], k, x, y->ch[0]); } o->maintain(); } } Node *merge(Node *x, Node *y) { if(x == null) return y; if(y == null) return x; if(x->rnd < y->rnd) { x->ch[1] = merge(x->ch[1], y); x->maintain(); return x; } else { y->ch[0] = merge(x, y->ch[0]); y->maintain(); return y; } } Node *build(int l, int r) { if(l > r) return null; int mid = (l + r) >> 1; Node *cur = newNode(qwq[mid], mid); if(l < r) { cur->ch[0] = build(l, mid - 1); cur->ch[1] = build(mid + 1, r); } cur->maintain(); return cur; } Node *kth(Node *o, int k) { if(k <= o->ch[0]->siz) return kth(o->ch[0], k); if(k == o->ch[0]->siz + 1) return o; return kth(o->ch[1], k - o->ch[0]->siz - 1); } void top(int p) { split(root, a[p], x, y); split(x, a[p] - 1, x, z); z->val = --curminv; a[p] = curminv; root = merge(merge(z, x), y); } void bottom(int p) { split(root, a[p], x, y); split(x, a[p] - 1, x, z); z->val = ++curmaxv; a[p] = curmaxv; root = merge(merge(x, y), z); } void insert(int p, int t) { if(t == 0) return; if(t == 1) { split(root, a[p], x, y); split(x, a[p] - 1, x, z); Node *qaq = kth(y, 1); split(y, qaq->val, y, r); a[p] = y->val; a[y->idx] = z->val; swap(y->val, z->val); root = merge(merge(x, y), merge(z, r)); } else { split(root, a[p], x, y); split(x, a[p] - 1, x, z); Node *qaq = kth(x, x->siz); split(x, qaq->val - 1, x, r); a[p] = r->val; a[r->idx] = z->val; swap(r->val, z->val); root = merge(merge(x, z), merge(r, y)); } } void ask(int p) { split(root, a[p] - 1, x, y); printf("%d\n", x->siz); root = merge(x, y); } void query(int p) { printf("%d\n", kth(root, p)->idx); } int main() { ///freopen("make.in", "r", stdin); ///freopen("debug.out", "w", stdout); n = read(), m = read(); init(); srand(time(0)); for(int i = 1; i <= n; ++i) { int tmp = read(); a[tmp] = i; // 编号为tmp的书优先级为i qwq[i] = tmp; // 优先级为i的是编号为tmp的书 } root = build(1, n); while(m--) { scanf("%s", c + 1); int ta = read(); // printf("qwq %d\n", root->siz); if(c[1] == 'T') {top(ta); continue;} if(c[1] == 'B') {bottom(ta); continue;} if(c[1] == 'I') {int tb = read(); insert(ta, tb); continue;} if(c[1] == 'A') {ask(ta); continue;} if(c[1] == 'Q') {query(ta);} } return 0; } /* 10 10 1 3 2 7 5 8 10 4 9 6 Ask 6 Bottom 3 Ask 3 ASK 9 10 10 1 3 2 7 5 8 10 4 9 6 Top 5 Ask 6 Bottom 3 Ask 3 Top 6 Insert 4 -1 Query 5 Query 2 Ask 2 10 10 1 3 2 7 5 8 10 4 9 6 Query 3 Top 5 Ask 6 Bottom 3 Ask 3 Top 6 Insert 4 -1 Query 5 Query 2 Ask 2 *//* 10 11 1 3 2 7 5 8 10 4 9 6 BOP 2 Qsk 1 Qsk 2 QSK 3 Qry 4 Query 5 Query 6 Query 7 Query 8 Query 9 Query 10 */

1
说点什么

avatar
1 Comment threads
0 Thread replies
1 Followers
 
Most reacted comment
Hottest comment thread
1 Comment authors
DefFrancis Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
DefFrancis
游客

窝不会秒切题,真的!