题解 P3960 【列队】

Nemlit

2019-04-29 10:08:03

Solution

## [原文地址](https://www.cnblogs.com/bcoier/p/10788767.html) 考虑转化题意: 设这次操作删掉点$(x, y)$ 对于每一次向左看齐:在第x行删除$(x, y)$,并将y以后的点全部前移一位 对于每一次向前看齐:x以后的点全部上移一位,并在最后一列插入$(x, y)$ 这些操作都可以用$Splay$解决: 我们开$N+1$棵$Splay$,1到N棵表示的是第i行,[1,m-1]的位置,第$N+1$棵表示最后一列的位置 这样我们可以把所有的点都扔进**一棵**$Splay$里面 题意有一次转化成: 设这次操作删掉点$(x, y)$ 对于每一次向左看齐:在第x棵$Splay$删除排名为$y$的节点,再将N+1棵$Splay$内的排名为$x$的节点删除并插入到第x棵$Splay$中 对于每一次向前看齐:在第$N+1$棵$Splay$中插入$(x, y)$ 但是这样的空间复杂度开销很大($NM$),显然不能过这道题 发现询问次数不多,而每一次询问需要动的点也很少,所以每一棵$Splay$里面存的节点变成了一个区间 每一次删除把区间分成3份:l ~ pos - 1, pos ~ pos, pos + 1 ~ r 删掉中间一份即可 ``` #include<bits/stdc++.h> using namespace std; #define il inline #define re register #define debug printf("Now is Line : %d\n",__LINE__) #define file(a) freopen(#a".in","r",stdin);freopen(#a".out","w",stdout) #define LL long long il int read() { re int x = 0, f = 1; re char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar(); return x * f; } #define rep(i, s, t) for(re int i = s; i <= t; ++ i) #define maxn 10000005 namespace splay { int fa[maxn], ch[2][maxn], rt[maxn], tot; #define pushup(x) size[x] = size[ch[0][x]] + size[ch[1][x]] + val[x].size #define get_fa(x) (ch[1][fa[x]] == x) LL size[maxn]; struct node { LL l, r, size; }val[maxn]; il void rotate(int x) { int y = fa[x], z = fa[y], w = get_fa(x), k = get_fa(y); ch[k][z] = x, fa[x] = z, ch[w][y] = ch[w ^ 1][x]; fa[ch[w ^ 1][x]] = y, ch[w ^ 1][x] = y, fa[y] = x; pushup(y), pushup(x); } il void Splay(int k, int x, int want) { while(fa[x] != want) { int y = fa[x]; if(fa[y] != want) rotate(get_fa(x) == get_fa(y) ? y : x); rotate(x); } if(!want) rt[k] = x; } il void insert(int k, LL x) { int u = rt[k], f = 0; while(u) f = u, u = ch[1][u]; u = ++ tot; size[u] = 1, fa[u] = f, val[u] = (node){x, x, 1}, ch[1][f] = u, Splay(k, u, 0); } il LL spilt(int p, int k, LL x) { LL s = val[k].l, t = val[k].r; if(s != x && t != x) { if(s + 1 < t) { int u = ++ tot; val[u].l = x + 1, val[u].r = val[k].r, val[u].size = (val[u].r - val[u].l + 1); val[k].r = x - 1, val[k].size = (val[k].r - val[k].l + 1); ch[1][u] = ch[1][k], ch[1][k] = u, fa[u] = k, Splay(p, u, 0); } else ++ val[k].l, -- val[k].size, Splay(p, k, 0); } else { if(s == x) ++ val[k].l; else -- val[k].r; -- val[k].size, Splay(p, k, 0); } return x; } il LL K_th(int k, int x) { int u = rt[k]; while(1) { if(size[ch[0][u]] >= x) u = ch[0][u]; else if(size[ch[0][u]] + val[u].size < x) x -= size[ch[0][u]] + val[u].size, u = ch[1][u]; else return spilt(k, u, x - size[ch[0][u]] + val[u].l - 1); } } } using namespace splay; int n, m, q; signed main() { n = read(), m = read(), q = read(); rep(i, 1, n) { rt[i] = ++ tot, val[tot].size = m - 1; val[tot].l = 1ll * (i - 1ll) * m + 1ll, val[tot].r = 1ll * i * m - 1ll; } rep(i, 1, n) insert(0, 1ll * i * m); while(q --) { int x = read(), y = read(); if(y == m) { LL u = K_th(0, x); printf("%lld\n", u), insert(0, u); } else { LL u = K_th(x, y); printf("%lld\n", u), insert(x, K_th(0, x)), insert(0, u); } } return 0; } ```