华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1266|回复: 4
打印 上一主题 下一主题

NOIP2017 列队(洛谷3960)(Day2 T3)

[复制链接]

5

主题

21

帖子

63

积分

华一学生

积分
63
跳转到指定楼层
楼主
发表于 2018-6-11 13:15:22 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
本帖最后由 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
回复

使用道具 举报

5

主题

21

帖子

63

积分

华一学生

积分
63
沙发
 楼主| 发表于 2018-6-11 13:23:58 | 只看该作者
在解决这个题目之前,建议先掌握Splay的一些基本操作。
我们仔细观察,发现如果每一行看作一个整体,设计到的操作是将第x行的y点删除,在最后一行的末尾插入节点
可以佷容易想到用splay来维护
但是这样空间复杂度O(nm)
我们又可以发现又许多节点始终都是相邻的,这样的节点可以合并
所以最终的时间复杂度为O(nlogn)空间足够,虽然splay常数较大,但还是能通过此题
回复 支持 反对

使用道具 举报

5

主题

21

帖子

63

积分

华一学生

积分
63
板凳
 楼主| 发表于 2018-6-11 13:25:56 | 只看该作者
  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大佬%%%%%
回复 支持 反对

使用道具 举报

5

主题

21

帖子

63

积分

华一学生

积分
63
地板
 楼主| 发表于 2018-6-11 13:29:40 | 只看该作者
本题还有线段树|树状数组的解法,但我还没有理解,等我搞明白后再把代码也贴上去
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
5#
发表于 2018-6-15 08:35:14 来自手机 | 只看该作者
写的很好!再写下线段树 的解法 加深理解
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 02:52 , Processed in 0.103150 second(s), 25 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表