「NOIP2017」列队 - 线段树

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

LibreOJ 链接

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

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

Sylvia 所在的方阵中有 \(n \times m\) 名学生，方阵的行数为 \(n\)，列数为 \(m\)。

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

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

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

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

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

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

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

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

解题思路

这道题直接模拟显然超时，通过分析题目，我们可以发现修改都与 \(m\) 列、当前点和最后一个点有关，于是我们可以建 \(n + 1\) 颗线段树来存储状态。其中前 \(n\) 颗存储 \(n\) 行目前的状态，用第 \(n + 1\) 棵存储第 \(m\) 行的状态。每个线段树只需记录该点是否存在即可。删除点在线段树对应点打上标记，添加点则增加每行计数即可，这样我们就可以知道每行有多少个点，以及可以查询每行第几个点在线段树中的坐标。而对于每行线段树前 \(m - 1\) 个点，我们显然可以直接推出；而对于之后的新添加点，我们可以在每一行建一个 std::vector 来存储新建节点的编号。由于询问次数小于 \(3 \times 10^5\) 故该方法可行。最后我们只需要对 \(y = m\) 的情况特判即可。

代码演示

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <cstdio>
#include <iostream>
#include <vector>

const int MAXN = 3e5;

struct SegT {
    int l, r;
    SegT *lc, *rc;
    long long val;

    SegT(int l, int r, SegT *lc, SegT *rc) : l(l), r(r), lc(lc), rc(rc), val(0) {}

    static SegT *build(const int l, const int r) { return new SegT(l, r, NULL, NULL); }

    void update(const int pos, const long long delta) {
        if (pos > r || pos < l)
            return;
        else if (pos == l && pos == r)
            val += delta;
        else {
            int mid = (l + r) / 2;
            if (pos <= mid) {
                if (!lc) lc = build(l, mid);
                lc->update(pos, delta);
            } else {
                if (!rc) rc = build(mid + 1, r);
                rc->update(pos, delta);
            }
            val = 0;
            if (lc) val += lc->val;
            if (rc) val += rc->val;
        }
    }

    int query(const int pos) {
        if (l == r)
            return l;
        else {
            if (!lc) lc = SegT::build(l, (l + r) / 2);
            int lSize = (r - l) / 2 + 1 + lc->val;
            if (pos <= lSize)
                return lc->query(pos);
            else {
                if (!rc) rc = SegT::build((l + r) / 2 + 1, r);
                return rc->query(pos - lSize);
            }
        }
    }
} *seg[MAXN + 2];

int main() {
    int n, m, q;

    scanf("%d %d %d", &n, &m, &q);
    int max = std::max(n, m) + q;
    for (int i = 1; i <= n + 1; i++) seg[i] = SegT::build(1, max);

    static std::vector<long long> tail[MAXN + 2];
    while (q--) {
        int x, y;
        scanf("%d %d", &x, &y);

        long long res = 0, val = 0;
        if (y != m) {
            int pos = seg[x]->query(y);
            seg[x]->update(pos, -1);
            res = pos < m ? (1ll * (x - 1) * m + pos) : (tail[x][pos - m]);
            val = res;
            printf("%lld\n", res);
        }

        int pos = seg[n + 1]->query(x);
        seg[n + 1]->update(pos, -1);
        res = pos <= n ? (1ll * pos * m) : tail[n + 1][pos - n - 1];
        tail[n + 1].push_back(val ? val : res);
        if (y == m)
            printf("%lld\n", res);
        else
            tail[x].push_back(res);
    }

    return 0;
}