NOIP2017 列队（洛谷3960）（Day2 T3）

WWX

Description

Sylvia 是一个热爱学习的女♂孩子。

前段时间，Sylvia 参加了学校的军训。众所周知，军训的时候需要站方阵。

Sylvia 所在的方阵中有 n×m 名学生，方阵的行数为 n ，列数为 m 。

为了便于管理，教官在训练开始时，按照从前到后，从左到右的顺序给方阵中 的学生从 1 到 n×m 编上了号码（参见后面的样例）。即：初始时，第 i 行第 j 列 的学生的编号是 (i−1)×m+j 。

然而在练习方阵的时候，经常会有学生因为各种各样的事情需要离队。在一天 中，一共发生了 q 件这样的离队事件。每一次离队事件可以用数对 (x,y)(1≤x≤n,1≤y≤m)描述，表示第 x 行第 y 列的学生离队。

在有学生离队后，队伍中出现了一个空位。为了队伍的整齐，教官会依次下达 这样的两条指令：

向左看齐。这时第一列保持不动，所有学生向左填补空缺。不难发现在这条 指令之后，空位在第 x 行第 m 列。

向前看齐。这时第一行保持不动，所有学生向前填补空缺。不难发现在这条 指令之后，空位在第 n 行第 m 列。

教官规定不能有两个或更多学生同时离队。即在前一个离队的学生归队之后， 下一个学生才能离队。因此在每一个离队的学生要归队时，队伍中有且仅有第 n 行 第 m 列一个空位，这时这个学生会自然地填补到这个位置。

因为站方阵真的很无聊，所以 Sylvia 想要计算每一次离队事件中，离队的同学 的编号是多少。

注意：每一个同学的编号不会随着离队事件的发生而改变，在发生离队事件后 方阵中同学的编号可能是乱序的。

Input

输入共 q+1 行。

第 1 行包含 3 个用空格分隔的正整数 n,m,q ，表示方阵大小是 n 行 m 列，一共发生了 q 次事件。

接下来 q 行按照事件发生顺序描述了 q 件事件。每一行是两个整数 x,y ，用一个空格分隔，表示这个离队事件中离队的学生当时排在第 x 行第 y 列。

Output

按照事件输入的顺序，每一个事件输出一行一个整数，表示这个离队事件中离队学 生的编号。

Range

对于 100% 的数据，n≤3×105,m≤3×105,q≤3×105

数据保证每一个事件满足 1≤x≤n,1≤y≤m

admin

写的很好！再写下线段树 的解法 加深理解

WWX

本题还有线段树｜树状数组的解法，但我还没有理解，等我搞明白后再把代码也贴上去

WWX

1. # include<iostream>
   
2. # include<cstdio>
   
3. # include<algorithm>
   
4. # include<cmath>
   
5. const int mn = 3000500;
   
6. typedef long long LL;
   
7. inline int read()
   
8. {
   
9.     int x=0;
   
10.     char ch=getchar();
    
11.     while(ch>'9' || ch<'0') ch=getchar();
    
12.     while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
    
13.     return x;
    
14. }
    
15. int n,m,q;
    
16. int fa[mn],son[mn][2],cnt;
    
17. LL l[mn],r[mn],siz[mn]; //l, r表示区间左右端点，此处左闭右开（个人习惯）
    
18. struct Splay{
    
19. int root;
    
20. inline int newNode(LL ll, LL rr) {    //ll, rr表示新节点的区间左右端点
    
21.       ++cnt;
    
22.       fa[cnt] = son[cnt][0] = son[cnt][1] = 0;
    
23.       siz[cnt] = (r[cnt] = rr) - (l[cnt] = ll);
    
24.       return cnt;
    
25. }
    
26. inline void init(LL ll, LL rr) {      //初始化树，只有一个对应[ll,rr)的根节点。
    
27.       root = newNode(ll, rr);
    
28. }
    
29. inline void upd(int x) { siz[x] = siz[son[x][0]] + siz[son[x][1]] + r[x] - l[x]; }
    
30. inline int dir(int x) { return son[fa[x]][1] == x; }    //x是fa[x]的哪个儿子
    
31. inline void rotate(int x) {
    
32.       int d = dir(x), f = fa[x];
    
33.       fa[x] = fa[f];
    
34.       if (f == root) root = x;
    
35.       else son[fa[f]][dir(f)] = x;
    
36.       if (son[f][d] = son[x][d ^ 1]) fa[son[f][d]] = f;
    
37.       fa[son[x][d ^ 1] = f] = x;
    
38.       upd(f);
    
39.       upd(x);
    
40. }
    
41. void splay(int x) {
    
42.       for (; fa[x]; rotate(x))
    
43.         if (fa[fa[x]]) rotate(dir(x) == dir(fa[x]) ? fa[x] : x);
    
44.     }
    
45. int splitNode(int x, LL k) {  //把节点x分裂，分裂后x的区间里前k个数还在x节点上，
    
46.       k += l[x];                  //后边的数对应新节点（即该函数返回值）
    
47.       int y = newNode(k, r[x]);
    
48.       r[x] = k;
    
49.       if (son[x][1] == 0) {
    
50.         fa[son[x][1] = y] = x;
    
51.       } else {
    
52.         int t = son[x][1];
    
53.         while (son[t][0]) t = son[t][0];
    
54.         fa[son[t][0] = y] = t;
    
55.         while (t != x) upd(t), t = fa[t];
    
56.       }
    
57.       splay(y);
    
58.       return y;
    
59. }
    
60. LL popKth(LL k) {             //弹出第k大数
    
61.       int o = root;
    
62.       while (1) {
    
63.         if (siz[son[o][0]] >= k) {
    
64.           o = son[o][0];
    
65.         } else {
    
66.           k -= siz[son[o][0]];
    
67.           if (k <= r[o] - l[o]) {
    
68.             if (k != r[o] - l[o]) splitNode(o, k);
    
69.             if (k != 1) o = splitNode(o, k - 1);
    
70.             break;
    
71.           } else {
    
72.             k -= r[o] - l[o];
    
73.             o = son[o][1];
    
74.           }
    
75.         }
    
76.       }
    
77.       splay(o);
    
78.       fa[son[o][0]] = fa[son[o][1]] = 0;
    
79.       if (!son[o][0]) {           //splay删除
    
80.         root = son[o][1];
    
81.       } else {
    
82.         int t = son[o][0];
    
83.         while (son[t][1]) t = son[t][1];
    
84.         splay(t);
    
85.         upd(root = fa[son[t][1] = son[o][1]] = t);
    
86.       }
    
87.       return l[o];
    
88. }
    
89. void pushBack(LL k){         //尾部插入数k
    
90.       int y = newNode(k, k + 1);
    
91.       if (!root) {
    
92.         root = y;
    
93.       } else {
    
94.         int o = root;
    
95.         while (son[o][1]) o = son[o][1];
    
96.         splay(o);
    
97.         upd(fa[son[o][1] = y] = o);
    
98.       }
    
99.     }
    
100. };
     
101. Splay s[mn];
     
102. int main() {
     
103.     cnt = 0;
     
104.     n=read(),m=read(),q=read();
     
105.     for (LL i=1;i<= n;++i) s[i].init((i - 1) * m + 1, i * m);
     
106.     s[0].init(m, m + 1);
     
107.     for (LL i = 2; i <= n; ++i) s[0].pushBack(i * m);
     
108.     int x, y;
     
109.     LL p;
     
110.     while (q--) {
     
111.       x=read(),y=read();
     
112.       s[x].pushBack(s[0].popKth(x));
     
113.       printf("%lld\n", p = s[x].popKth(y));
     
114.       s[0].pushBack(p);
     
115.     }
     
116.     return 0;
     
117. }
     

复制代码

代码参考了rqy大佬%%%%%

WWX

在解决这个题目之前，建议先掌握Splay的一些基本操作。
我们仔细观察，发现如果每一行看作一个整体，设计到的操作是将第x行的y点删除，在最后一行的末尾插入节点
可以佷容易想到用splay来维护
但是这样空间复杂度O（nm）
我们又可以发现又许多节点始终都是相邻的，这样的节点可以合并
所以最终的时间复杂度为O（nlogn）空间足够，虽然splay常数较大，但还是能通过此题