F题题解

我们用一张按起点排序的有序映射来维护所有已经被赋值过的区间，每个映射项记录该区间的终点和对应的值。在对任意区间 [l,r] 执行赋值操作之前，先在 l 和 r+1 处将可能跨越端点的原有区段一分为二，这样就能保证待修改区间恰好由若干完整的映射段组成；然后依次删除这些旧段，同时在一个哈希表中扣减相应值的元素个数，如果某个非零值的计数变为零，就将当前不同元素种类数减一。删除完毕后，再在起点 l 处插入一个新段，长度为 r−l+1，如果新值此前未出现过，就先将种类数加一，再把该区间长度加入该值的计数中。

由于数组在最大索引之后默认都是零，所以我们一开始就把整个 [1, N] 区间初始化为值 0，并在计数时无论零的个数如何变化都不减少种类数，保证零始终被视为一种存在的值。所有的分段、删除和插入操作都在 map 上以对数时间完成，每个段最多被拆分和删除一次，因此总体能够在 O(q log q) 时间内处理完毕，并在每次操作后常数时间地输出当前不同元素的种类数。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Seg {int r; int v;};                 // 颜色段：终点、颜色
map<int, Seg> seg;                          // key = 段起点
unordered_map<ll,ll> cnt;                   // 颜色 -> 数量
int kinds = 1;                              // 目前不同元素种类数(含 0)
const int N = 100000;                       // 题目保证 r ≤ 1e5

// 在 pos 处断开颜色段并返回右段迭代器
auto split(int pos){
    auto it = seg.lower_bound(pos);
    if (it != seg.end() && it->first == pos) return it;
    --it;                                   // now it->first < pos ≤ it->second.r
    int l = it->first, r = it->second.r, v = it->second.v;
    if (pos > r) return seg.end();
    it->second.r = pos - 1;                 // 左段变短
    return seg.insert({pos, {r, v}}).first; // 插入右段
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;  if(!(cin >> q)) return 0;

    seg[1] = {N, 0};                        // 初始整段为 0
    cnt[0] = N;                             // 0 在 [1,N] 内出现 N 次

    while (q--){
        int l, r, x; cin >> l >> r >> x;
        auto itR = split(r + 1);
        auto itL = split(l);

        // 删除被覆盖的旧段
        for (auto it = itL; it != itR; ){
            int len = it->second.r - it->first + 1;
            int v   = it->second.v;
            if (v != 0){
                cnt[v] -= len;
                if (cnt[v] == 0) kinds--;
            }
            it = seg.erase(it);
        }

        // 插入新区间
        seg[l] = {r, x};
        if (x != 0){
            if (cnt[x] == 0) kinds++;
            cnt[x] += (r - l + 1);
        }
        cout << kinds << '\n';
    }
    return 0;
}