题解
是我从来没有做过的裂点splay。。。 看的时候还是很懵逼的QAQ。
把最后一列的$n$个数放在一个平衡树中， 有 $n$ 个点
剩下的$n$行数， 每行都开一个平衡树，开始时每棵树中仅有$1$个点， 记录了开始时的区间左端点 $1$ 和右端点$m - 1$。
这样每次出队都最多只会影响两棵平衡树， 其中一颗为表示最后一列的平衡树。
然后就可以分成两种情况进行处理
1. $y = m$ 即出队的人位于最后一列，那么仅会影响最后一列的那颗平衡树， 删除位于第$x$个位置的点， 再插入到最后即可
2. $y \ne m$ 首先把最后一列的平衡树的第$x$个节点 $tmp$ 删除，
然后将第$x$棵平衡树 分成$[1,y - 1]$,$ y $,$ [y +1,m - 1] $三个区间， 再将y删除并插入到 最后一列平衡树的最后。
最后再把tmp插入到第$x$ 棵平衡树的最后。
虽然看起来很暴力， 但因为我太弱还是想不到TAT
代码
1 #include2 #include 3 #include 4 #define rd read() 5 #define ri register int 6 #define il inline 7 using namespace std; 8 typedef long long ll; 9 10 const int N = 3e5 + 1e4; 11 12 int sz[N << 3], cnt[N << 3], l[N << 3], r[N << 3], root[N]; //root为每颗平衡树的根节点 13 int ch[N << 3][2], f[N << 3]; 14 ll key[N << 3];//key为节点对应的人的编号 15 int n, m, q, tot; 16 17 int read() { 18 int X = 0, p = 1; char c = getchar(); 19 for(; c > '9' || c < '0'; c = getchar() ) if( c == '-' ) p = -1; 20 for(; c >= '0' && c <= '9'; c = getchar() ) X = X * 10 + c - '0'; 21 return X * p; 22 } 23 24 il void update( int x ) { 25 sz[x] = cnt[x]; 26 sz[x] += sz[ch[x][0]] + sz[ch[x][1]]; 27 } 28 29 il int get( int x ) { 30 return ch[f[x]][1] == x; 31 } 32 33 int build( int l, int r , int fa ) { //最后一列的平衡树 34 if( l > r ) return 0; 35 int mid = (l + r) >> 1; 36 sz[mid] = cnt[mid] = 1; 37 key[mid] = 1LL * mid * m;//编号 38 f[mid] = fa; 39 ch[mid][0] = build( l, mid - 1, mid ); 40 ch[mid][1] = build( mid + 1, r, mid ); 41 update(mid); 42 return mid; 43 } 44 45 void rotate( int x ) { 46 int old = f[x], oldf = f[old], son = ch[x][get(x) ^ 1]; 47 if(oldf) ch[oldf][get(old)] = x; 48 ch[x][get(x) ^ 1] = old; 49 ch[old][get(x)] = son; 50 f[old] = x; f[x] = oldf; 51 if(son) f[son] = old; 52 update(old); update(x); 53 } 54 55 void splay( int x, int id ) { //id表示平衡树的编号 56 for( int fa; (fa = f[x]); rotate(x)) 57 if(f[fa]) rotate(get(fa) == get(x) ? fa : x); 58 root[id] = x; 59 } 60 61 int findk( int k , int now ) { //查询最后一列的平衡树中的第k个点 62 for(; ;) { 63 if( k <= sz[ch[now][0]] ) now = ch[now][0]; 64 else if( k == sz[ch[now][0]] + cnt[now] ) return now; 65 else { 66 k -= sz[ch[now][0]] + cnt[now]; 67 now = ch[now][1]; 68 } 69 } 70 } 71 72 void insert_last( int id, ll x ) { //向第id棵平衡树的末尾插入key为x 的点 73 if(!root[id]) { 74 root[id] = ++tot; 75 key[tot] = x; 76 sz[tot] = cnt[tot] = 1; 77 ch[tot][0] = ch[tot][1] = 0; 78 return; 79 } 80 int now = root[id]; 81 for(; ch[now][1]; now = ch[now][1] ); 82 f[++tot] = now; 83 ch[tot][0] = ch[tot][1] = 0; 84 ch[now][1] = tot; 85 sz[tot] = cnt[tot] = 1; 86 key[tot] = x; 87 update(now); 88 splay(tot, id); 89 } 90 91 int pre( int id ) { //前驱 92 int now = ch[root[id]][0]; 93 for(; ch[now][1]; now = ch[now][1] ); 94 return now; 95 } 96 97 void del( int id ) { //删除第id棵平衡树的根节点 98 int rt = root[id]; 99 if(!ch[rt][0] && !ch[rt][1]) {100 root[id] = 0;101 return;102 }103 if(!ch[rt][0]) {104 root[id] = ch[rt][1];105 f[root[id]] = 0;106 return;107 }108 if(!ch[rt][1]) {109 root[id] = ch[rt][0];110 f[root[id]] = 0;111 return;112 }113 int pr = pre(id);114 splay(pr, id);115 ch[pr][1] = ch[rt][1];116 f[ch[rt][1]] = pr;117 update(pr);118 }119 120 void split( int k, int now, int id ) { //将第id棵平衡树分裂121 if( k <= sz[ch[now][0]] ) {122 split(k, ch[now][0], id);123 return;124 }125 if( k > sz[ch[now][0]] + cnt[now] ) {126 split(k - sz[ch[now][0]] - cnt[now], ch[now][1], id);127 return;128 }129 k -= sz[ch[now][0]];130 if( k != 1 ) {131 sz[++tot] = k - 1;132 cnt[tot] = k - 1;133 f[tot] = now;134 cnt[now] -= k - 1;135 ch[tot][0] = ch[now][0];136 f[ch[now][0]] = tot;137 ch[now][0] = tot;138 l[tot] = l[now];139 r[tot] = l[tot] + k - 2;140 l[now] = r[tot] + 1;141 update(tot);142 }143 if(cnt[now] != 1) {144 sz[++tot] = cnt[now] - 1;145 cnt[tot] = cnt[now] - 1;146 f[tot] = now;147 cnt[now] = 1;148 ch[tot][1] = ch[now][1];149 f[ch[now][1]] = tot;150 ch[now][1] = tot;151 r[tot] = r[now];152 r[now] = l[now];153 l[tot] = l[now] + 1;154 update(tot);155 }156 splay(now, id);157 }158 159 int main()160 {161 n = rd, m = rd; q = rd;162 root[0] = build( 1, n, 0);163 tot = n;164 for( int i = 1; i <= n; ++i ) {165 root[i] = ++tot;166 sz[tot] = cnt[tot] = m - 1;167 l[tot] = 1; r[tot] = m - 1;168 }169 for(; q; --q ) {170 int x = rd, y = rd, tmp = findk(x, root[0]);171 ll ans;172 splay(tmp, 0);173 del(0);//删除tmp174 if( y != m ) {175 split(y, root[x], x);176 int rt = root[x];177 if(!key[rt]) key[rt] = 1LL * (x - 1) * m + l[rt];178 ans = key[rt];179 del(x);180 insert_last(x, key[tmp]);//向第x棵平衡树插入，表示左移181 insert_last(0, ans);//向最后一列的平衡树插入，表示将位于x,y的人拉到最后182 }183 else {184 insert_last(0, key[tmp]);185 ans = key[tmp];186 }187 printf("%lld\n", ans);188 }189 }
更新。。。
用动态开点线段树做了一波
和splay差不多的思想， 先不把线段树中的点都开满，有$N+1$个空树。
定义$sum$为删除的数，每次查询第$k$个数时， 把$k$与 mid - l + 1 - sum[lson[nd]] 进行比较， 进入相应子树继续查询。
添加时就用vector插入。
删除时只要添加节点并记录
1 #include2 #include 3 #include 4 #include 5 #define ll long long 6 #define rd read() 7 using namespace std; 8 9 const int N = 3e6;10 11 int n, m, q, tot;12 int rt[N << 3], ls[N << 3], rs[N << 3], sum[N << 3];13 int pos, mx;14 15 vector v[N];16 17 int read() {18 int X = 0, p = 1; char c = getchar();19 for(; c > '9' || c < '0'; c = getchar()) if(c == '-') p = -1;20 for(; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';21 return X * p;22 }23 24 void change(int &o, int l, int r) {25 if(!o) o = ++tot;26 sum[o]++;27 if(l == r) return;28 int mid = (l + r) >> 1;29 if(pos <= mid) change(ls[o], l, mid);30 else change(rs[o], mid + 1, r);31 }32 33 int query(int nd, int l, int r, int k) {34 if(l == r) return l;35 int mid = (l + r) >> 1, tmp = mid - l + 1 - sum[ls[nd]];36 if(k <= tmp) return query(ls[nd], l, mid, k);37 else return query(rs[nd], mid + 1, r, k - tmp);38 }39 40 ll work1(int x, ll y) {41 pos = query(rt[n + 1], 1, mx, x);42 change(rt[n + 1], 1, mx);43 ll ans = pos <= n ? 1LL * m * pos : v[n + 1][pos - n - 1]; 44 v[n + 1].push_back(y ? y : ans);45 return ans;46 }47 48 ll work2(int x, int y) {49 pos = query(rt[x], 1, mx, y);50 change(rt[x], 1, mx);51 ll ans = pos < m ? 1LL * (x - 1) * m + pos : v[x][pos - m];52 v[x].push_back(work1(x, ans));53 return ans;54 }55 56 int main()57 {58 n = rd; m = rd; q = rd;59 mx = max(n, m) + q;60 for(; q; q--) {61 int x = rd, y = rd;62 if(y == m) printf("%lld\n", work1(x, 0));63 else printf("%lld\n", work2(x, y));64 }65 }