题解 CF899E 【Segments Removal】

· · 题解

双向链表 堆

背景

神犇们都道是 \mathtt{Splay} 模板题，可是小萌新 \varnothing 实在是太菜了，他只会使用优先队列。

思路

很明显，数列 a 是由若干段区间组成，每一段区间数字相同，以下均用“颜色”表示每一段区间的数字（属性）。

先不考虑如何实现，我们先考虑思路：

  1. 从当前所有区间中找出长度最大的（相同长度找最左边的），记为区间 cur，删除，计数器+1；

  2. 判断 cur 的左右区间颜色是否相同，若相同，将两个小区间的信息删除，插入合并后的大区间的信息；

  3. 检查是否全部删除完了，没删完则重复步骤1，否则结束。

不考虑步骤2，这个过程显然可以用优先队列维护，步骤1即取出堆顶，步骤3检查堆是否为空。

直接从堆中找出左右两个元素是十分麻烦的，删除更是没法做。

删除区间 cur，查找区间 cur 当前的左右区间，显然可以用双向链表维护。

对于删除堆中的元素，我们可以用 vis 标记这个元素在堆中已经被删除了，若堆顶元素被标记过，直接continue掉即可。

维护一个双向链表，链表中每个节点储存【该区间是初始情况中从左往右第 i 个区间】，pre[i] 表示 i 左边的区间编号，nxt[i] 表示 i 右边的区间编号。

维护一个优先队列，堆中每节点储存【区间长度，区间编号】，先按照第一维由大到小排序，第一维相同时第二维从小到大排序（左边优先）。

  1. 设当前堆顶区间的编号是 cur，我们需要在链表中删除 cur，并标记 vis；

  2. 若 pre[cur] 与 nxt[cur] 颜色相同，则标记 vis 表示删除了右区间，将【左右区间长度之和，左区间编号】加入优先队列中；

加入后，堆中会有两个节点编号都为左区间编号，不过不要紧，因为新加入那个区间长度更大，会被更早取出，取出时标记 vis。

  1. 计数器+1，这回合删除了一个区间。

代码

实现时，由于先按第一维升序，再按第二维降序比较麻烦，我们不妨直接将数列 a 翻转过来（倒序输入），这样两维都是升序了。

#include <queue>
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 200005;
int n, a[maxn], tot, col[maxn], sum[maxn], pre[maxn], nxt[maxn], ans;
bool vis[maxn];
priority_queue<pair<int, int> > q;
int main() {
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = n; i; --i) cin >> a[i];
    for(int i = 1; i <= n; ++i)
        if(a[i] == a[i-1]) ++sum[tot];
        else col[++tot] = a[i], sum[tot] = 1;
    for(int i = 1; i <= tot; ++i) pre[i] = i-1, nxt[i] = i+1, q.push(make_pair(sum[i], i));
    while(!q.empty()) {
        int cur = q.top().second; q.pop();
        if(vis[cur]) continue;
        int l = pre[cur], r = nxt[cur];
        pre[r] = l, nxt[l] = r, vis[cur] = true;
        if(l and col[l] == col[r])
            pre[nxt[r]] = l, nxt[l] = nxt[r], vis[r] = true, q.push(make_pair(sum[l]+=sum[r], l));
        ++ans;
    }
    cout << ans << endl;
}

p.s

小萌新yy的做法，有hack数据叫我嗷。