easy 与 hard 的唯一区别是$col_i$的范围。

Tokitsukaze 正在玩一个消除游戏。

初始有$n$个宝石从左到右排成一排,第$i$个宝石的颜色为$col_i$。Tokitsukaze 可以进行若干次以下操作: 任选一种颜色$x$,将颜色为$x$的最右边那颗宝石、以及该宝石右边的所有宝石全部消除。

Tokitsukaze 想知道至少需要几次操作才能把$n$个宝石全部消除。

输入格式

第一行包含一个整数$T (1≤T≤2⋅10^5)$,表示$T$组测试数据。

对于每组测试数据:

第一行包含一个整数$n (1≤n≤2⋅10^5)$,表示初始宝石的数量。 第二行包含$n$个整数$col_1, col_2,…,col_n (1≤col_i ≤n)$,表示每个宝石的颜色。

保证$\sum n$ 不超过 $2⋅10^5$。

输出格式

对于每组测试数据,输出一个整数,表示把$n$个宝石全部消除所需要的最少操作次数。

输入样例:

6
3
1 2 1
5
1 2 2 1 2
11
2 2 1 2 2 1 1 2 2 1 2
1
1
5
1 2 3 4 5
10
4 1 5 5 2 2 5 2 4 2

输出样例:

2
2
6
1
1
2

说明

第一组测试数据:

初始宝石为$[1,2,1]$;

第1次操作选择颜色2,可以消除最右边的2个宝石,当前剩余宝石为$[1]$; 第2次操作选择颜色1,即可把所有宝石都消除。

第三组测试数据:

初始宝石为$[2,2,1,2,2,1,1,2,2,1,2]$;

第1次操作选择颜色1,可以消除最右边的2个宝石,当前剩余宝石为$[2,2,1,2,2,1,1,2,2]$; 第2次操作选择颜色1,可以消除最右边的3个宝石,当前剩余宝石为$[2,2,1,2,2,1]$; 第3次操作选择颜色2,可以消除最右边的2个宝石,当前剩余宝石为$[2,2,1,2]$; 第4次操作选择颜色1,可以消除最右边的2个宝石,当前剩余宝石为$[2,2]$; 第5次操作选择颜色2,可以消除最右边的1个宝石,当前剩余宝石为$[2]$; 第6次操作选择颜色2,即可把所有宝石都消除。

第六组测试数据:

初始宝石为$[4,1,5,5,2,2,5,2,4,2]$; 第1次操作选择颜色5,可以消除最右边的4个宝石,当前剩余宝石为$[4,1,5,5,2,2]$; 第2次操作选择颜色4,即可把所有宝石都消除; 或者也可以这么操作:第1次操作选择颜色1,第2次操作选择颜色4; 还可以这么操作:第1次操作选择颜色4,第2次操作选择颜色4。

题目分析

分析题目我们可以知道,每次最优的选择是: 选择从右往左看最左边的第一次出现的宝石。

那么我们可以设法维护一个 从右往左看第一次出现的宝石 的集合。(从右往左遍历, 将第一次出现的宝石的坐标存到小根堆里,那么树根就是我们的最优选择)

那么怎么更新我们的这个小根堆呢?(选取树根进行消除操作后,小根堆的内容全部失效)

我们可以预先构造一个 ne 数组, 将每个位置的宝石的 ne 指向它的左边的第一个相同的宝石的位置。 那么在我们的消除操作后,我们只需要将小根堆全部倒出, 并按照 ne 构成下一个局面的从右往左看的第一次出现的宝石的小根堆集合。

接下来就是相同的迭代过程。

更优的做法是将元素对应的下标存在对应的栈中,每次取栈顶最小的坐标进行消除。

代码实现

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#define x first 
#define y second 
using namespace std;
using PII = pair <int,int>;
using LL = long long;
const int N = 2e5 + 10;

int t;
int solve() {
    int n, arr[N];
    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    priority_queue <PII, vector <PII>, greater <PII>> heap;
    unordered_map <int, int> fs, ne, ls;
    for (int i = n; i >= 1; --i) {
        if(fs.find(arr[i]) == fs.end()) {
            heap.push({i, arr[i]});
            fs[arr[i]] = i;
        }
    }
    for(int i = 1; i <= n; ++i) {
        if(ls.find(arr[i]) == ls.end()) {
            ls[arr[i]] = i;
            ne[i] = -1;
        }
        else {
            ne[i] = ls[arr[i]];
            ls[arr[i]] = i;
        }

    }
    int cnt = 0;
    int pos = n;
    while (pos >= 1) {
        ++cnt;
        priority_queue <PII, vector <PII>, greater <PII>> h;
        auto tt = heap.top();
        if(tt.x <= pos) pos = tt.x - 1;
        else break;
        while(!heap.empty()) {
            tt = heap.top(); heap.pop();
            int ps = tt.x, val = tt.y;
            while(tt.x > pos) tt.x = ne[tt.x];
            if(tt.x != -1) {
                h.push({tt.x, arr[tt.x]});
            }
        }
        heap = h;
    }
    return cnt;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while(t--) cout << solve() << '\n';
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status