我永远喜欢珂朵莉 --- luogu P13983 数列分块入门 8 题解

思路：

ODT（珂朵莉树） 的简单练手题。什么？你不会珂朵莉树？左转珂朵莉树模板题解。

先看题目给让我们实现的操作：

1. 找出区间相同值的个数。

2. 更改区间的值为一个相同的值。

欸？操作二对应的操作不就是 ODT 的区间推平吗？操作一对应的操作直接用 ODT 暴力不就行了？

也就是操作二使用区间推平，操作一直接用 ODT 暴力即可，但是要注意的是，操作一要是发现相同的值，当前应该加的是区间长度。

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct node {
    int l, r;
    mutable int v;
    node(int _l, int _r = -1, int _v = 0) : l(_l), r(_r), v(_v) {
    }
    friend bool operator<(node a, node b) {
        return a.l < b.l;
    }
};

set<node> s;

auto split(int pos) {
    auto it = s.lower_bound(node(pos, 0, 0));
    if (it != s.end() && it->l == pos) {
        return it;
    }
    it--;
    int l = it->l, t = it->r, v = it->v;
    s.erase(it), s.insert(node(l, pos - 1, v));
    return s.insert(node(pos, t, v)).first;
}

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    s.erase(itl, itr), s.insert(node(l, r, v));
}

int query(int l,int r,int v) {
    auto itr = split(r + 1), itl = split(l);
    int cnt = 0;
    for (auto it = itl; it != itr; it++) {
        if (it->v == v)cnt += (it->r - it->l + 1);// 注意这里
    }
    return cnt;
}

const int N = 1e6 + 5;
int n, a[N];

signed main() {
    cin >> n;
    s.insert(node(1, n, 0));
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        assign(i, i, a[i]);
    }
    int _ = n;
    for (; _--;) {
        int l, r, c;
        cin >> l >> r >> c;
        cout << query(l, r, c) << "\n";
        assign(l, r, c);
    }
    return 0;
}