[LOJ#6284.數列分塊入門8] ODT（珂朵莉樹）解法

題面：node

給出一個長爲 \(n\) 的數列，以及 \(n\) 個操做，操做涉及區間詢問等於一個數 \(c\) 的元素，並將這個區間的全部元素改成 \(c\)。c++

這道題我一看到區間推平就想到了 ODT，徹底無論這是一道分塊題。實際上，分塊能夠作的題， ODT 也基本能夠勝任。函數

問題是網上的博客基本沒有講到 ODT 的查詢操做，讓某些 抄題解過日子的 人無從下手。spa

因而你們就用了喜聞樂見的分塊，可是並很差打。我的認爲，珂朵莉樹碼量少是最大的優點，可能會被卡也無所謂 反正珂朵莉那麼可愛code

而後假設你們都知道 \(split\) 和 \(assign\) 操做的方法，在這裏就不贅述這些基礎的東西了。blog

首先考慮 \(set\) 內置的函數，可是 \(set::count()\) 沒法指定一個區間來進行計數，因此這個方法就馬上泡湯了。get

set內置函數已經 SPFA 了博客

而後就不會了。而後就是仿造區間加的模式套了一個 \(check(l,r,c)\) 的函數，以下。it

#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。io

事實上，應該加上的是這個以及推平的區間的元素數量，即 \(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");
}