题解：P13983 数列分块入门 8

lw393 · 2025-09-10 17:02:35 · 题解

ODT 入门。

我们考虑区间推平的总复杂度。

我们定义势能函数 \Phi(A) 为数组 A 的颜色段数。

对于 odt 的 split 操作，势能最多增加 2，而对于 [l,r] 区间内，势能会减少 \Phi(A_{[l,r]})-1，且会获得 O(\Phi(A_{[l,r]})) 的时间复杂度。

这样我们就会得到一个性质：势能只有在减少时会计入时间复杂度中，所以对于一个数组而言，我们会有时间复杂度应为总势能与势能修改量的和：T(n)=2n+\Phi(n)=O(n)，这里的分析基于 n,m 同阶且操作 O(1)。

然而 ODT 是带 \log 的，所以总时间复杂度应为 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
// warning! File IO!

struct node{
    int l, r, val;
    bool operator < (const node &x) const {
        return l < x.l;
    }
};

set<node>s;
int n;

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

int assign(int l, int r, int v) {
    int res = 0;
    auto itr = split(r + 1), itl = split(l);
    for(auto it = itl; it != itr; ++it) 
        if(it -> val == v) res += (it -> r - it -> l + 1);
    s.erase(itl, itr);
    s.insert({l, r, v});
    return res;
}

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x; s.insert({i, i, x});
    }
    for(int i = 1; i <= n; i++) {
        int l, r, v; cin >> l >> r >> v;
        cout << assign(l, r, v) << '\n';
    }
}

int main(){
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}