【题解】数列分块入门 8 ODT 解法 – Sora1336

题面：

给出一个长为 $n$ 的数列，以及 $n$ 个操作，操作涉及区间询问等于一个数 $c$ 的元素，并将这个区间的所有元素改为 $c$。

这道题我一看到区间推平就想到了 ODT，完全不管这是一道分块题。实际上，分块可以做的题， ODT 也基本可以胜任。

问题是网上的博客基本没有讲到 ODT 的查询操作，让某些 抄题解过日子的 人无从下手。

于是大家就用了喜闻乐见的分块，但是并不好打。个人认为，珂朵莉树码量少是最大的优势，可能会被卡也无所谓 反正珂朵莉那么可爱

然后假设大家都知道 $split$ 和 $assign$ 操作的方法，在这里就不赘述这些基础的东西了。

首先考虑 $set$ 内置的函数，但是 $set::count()$ 无法指定一个区间来进行计数，所以这个方法就立刻泡汤了。

set 内置函数已经 SPFA 了

然后就不会了。然后就是仿造区间加的模式套了一个 $check(l,r,c)$ 的函数，如下。

#define IT set<node>::iterator
int check(int l,int r,ll val=1){
    int ans=0;
    IT itl = split(l),itr = split(r+1);
    for (; itl != itr; ++itl) if(itl->v==val) ans++;
    return ans;
}

愉快的，我这个 抄题解过日子的屑 获得了 WA。

事实上，应该加上的是这个以及推平的区间的元素数量，即 $Now_{iter}\rightarrow r-Now_{iter}\rightarrow l+1$，即 itl->r-itl->l+1。

所以就改成了下面这个样子。

int check(int l,int r,ll val=1){
    int ans=0;
    IT itl = split(l),itr = split(r+1);
    for (; itl != itr; ++itl) if(itl->v==val) ans+=itl->r-itl->l+1;
    return ans;
}

完整代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    int l,r;
    mutable ll v;
    node(int L, int R=-1, ll V=0):l(L), r(R), v(V) {}
    bool operator<(const node& o) const{return l < o.l;}
};
set<node> ODT;
#define IT set<node>::iterator
IT split(int pos){
    IT it = ODT.lower_bound(node(pos));
    if (it != ODT.end() && it->l == pos) return it;
    --it;
    int L = it->l, R = it->r;
    ll V = it->v;
    ODT.erase(it);
    ODT.insert(node(L, pos-1, V));
    return ODT.insert(node(pos, R, V)).first;
}
int check(int l,int r,ll val=1){
    int ans=0;
    IT itl = split(l),itr = split(r+1);
    for (; itl != itr; ++itl) if(itl->v==val) ans+=itl->r-itl->l+1;
    return ans;
}
void assign(int l, int r, ll val=0){
    IT itl = split(l),itr = split(r+1);
    ODT.erase(itl, itr);
    ODT.insert(node(l, r, val));
}
int main(){
    int n,a;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        ODT.insert(node(i,i,a));
    }for(int i=1;i<=n;i++){
        int l,r;
        ll c;
        scanf("%d%d%lld",&l,&r,&c);
        printf("%d\n",check(l,r,c));
        assign(l,r,c);
    }//system("pause");
}

感谢你的阅读 qwq