华师一附中OI组

标题: NOIP2017 列队（洛谷3960）（Day2 T3） [打印本页]
作者: WWX    时间: 2018-6-11 13:15
标题: NOIP2017 列队（洛谷3960）（Day2 T3）
本帖最后由 WWX 于 2018-6-11 13:18 编辑

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
作者: WWX    时间: 2018-6-11 13:23
在解决这个题目之前，建议先掌握Splay的一些基本操作。
我们仔细观察，发现如果每一行看作一个整体，设计到的操作是将第x行的y点删除，在最后一行的末尾插入节点
可以佷容易想到用splay来维护
但是这样空间复杂度O（nm）
我们又可以发现又许多节点始终都是相邻的，这样的节点可以合并
所以最终的时间复杂度为O（nlogn）空间足够，虽然splay常数较大，但还是能通过此题
作者: WWX    时间: 2018-6-11 13:25
  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    时间: 2018-6-11 13:29
本题还有线段树｜树状数组的解法，但我还没有理解，等我搞明白后再把代码也贴上去
作者: admin    时间: 2018-6-15 08:35
写的很好！再写下线段树 的解法 加深理解



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2