P10688 Buy Tickets 题解

· · 题解

题意简述

要求做 n 次的插队操作，得出最终的序列。

思路解析

vector 做法解析（理论不可行）

第一眼看出这是一道模拟题，首要且唯一的难点就是如何实现插入操作。

STL库中，在 vector 中有 insert 操作可以实现插入，但它的时间复杂度是 O(n) 的，理论上，总体时间复杂度 O(n^2)，总体最大消耗时间约为 4 \times 10^{10}，不足以通过此题（但因为其 vector 在国内外程序开发的常用性，经过来自五湖四海的人士各种优化，加上编译器的优化，免去了 C++ 传统 STL 的常数极大的特性， vector 的 insert 操作常数极小，卡常或不卡常依旧可以通过此题）。

vector 做法代码实现

#pragma G++ optimize("O3", "unroll-loops", "omit-frame-pointer", "inline")
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    while (cin >> n) {
        a.clear();
        while (n--) {
            int x, y;
            cin >> x >> y;
            a.insert(a.begin() + x, y);
        }
        for (auto i : a) {
            cout << i << " ";
        }
        cout << '\n';
    }
    return 0;
}

块状链表做法解析

注意到这题并不需要查询，那么我们想到可以使用链表数据结构。然而，对于本题，我们需要在特定位置中插入元素，虽然链表的插入时间复杂度为 O(1)，但是它的访问时间是 O(n) 的。如何解决呢？

尺有所短，寸有所长。常规的数组用的多了，也要尝试其他的数据结构。我们可以使用块状链表。

插队的人的数字插入每个节点的数组，按题意模拟，并在适当的时候进行分裂等操作即可。

因为其运用了分块的思想，总体时间复杂度为 O(n \sqrt {n}) 或 O(n^{\frac{3}{2}})。因为本题 n \le 2 \times 10^5，理论总体最大消耗时间约为 9 \times 10^7，注意下常数可以通过此题。

你可以手动模拟，但是你也可以使用 pd_ds 库中的 rope 来实现该功能（下文会阐述时间复杂度）。

rope 做法代码实现

#pragma G++ optimize("O3", "unroll-loops", "omit-frame-pointer", "inline")
#include <bits/stdc++.h>
using namespace std;
#include <ext/rope>         //引入rope库
using namespace __gnu_cxx;  // rope所在的命名空间
int n;
list<vector<int>> a;  // 手动模拟块状链表
rope<int> l;
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    while (cin >> n) {
        l.clear();
        while (n--) {
            int x, y;
            cin >> x >> y;
            l.insert(x, y);
        }
        for (int i : l) {
            cout << i << " ";
        }
        cout << "\n";
    }
    return 0;
}

反而实际上更慢了。

平衡树做法解析（杀鸡焉用牛刀）

然而，很多人并不知道块状链表这一个数据结构，有没有什么其他的做法呢？

再看一眼，其实就是平衡树的模板题，你可以手动模拟，但在pd_ds 库中，有很多平衡树类型供你挑选，推荐还是 Splay 树（详见 OI Wiki 上的平衡树）。

当然了，你也可以用上文提到的 rope 来实现，因为它采用了可持久化平衡树实现，实际上每次是 O(\log n) 的。

平衡树代码实现

见上文块状链表 rope 做法代码实现。

线段树做法解析

从前往后的操作不利用以上的做法很难实现，那么我们可不可以使用逆向思维，从后往前操作呢？

明显地，能想到后插队的人是要比先排队的人的优先级要高的，这种做法是可行的。可以先行记下空白的位置（或说是区间），那么当插入的时候，就插入第几个空白的位置就可以了。

根据上面做法的经验，我们仅需一个能进行单点插入，和随机访问比较数据结构即可。对于区间，线段树在这里起到一个前缀和的查询的作用，可以满足我们的需求。

树状数组&二分做法解析

能用到线段树的题，很多也都可以用树状数组。在这里，树状数组做法和线段树做法是类似的，但是，注意到可以优化查询的过程，所以可以用二分的思想来查询第几个空白的位置。

后记

关于是否能使用这些简单好用的 STL 容器或函数，详见《关于NOI系列活动中编程语言使用限制的补充说明》。

由于机房的网上不了 POJ，对于原题数据的检测无法进行（待补）。

其实这几种思想是相似的，如果有其他更好的想法或做法可以在评论区指出。