你不会珂朵莉树也没关系,下面我会参考OI WiKi来讲解珂朵莉树。
名称由来:
珂朵莉树,又名老司机树 ODT(Old Driver Tree)。起源自 CF896C。
主要用途:
用于区间赋值操作的数据结构题。在数据随机的情况下一般效率较高,由于其本身是一种暴力求解,因此会被精心构造的特殊数据卡到超时。
实现方式:
为了更好地理解,我们引入例题来进行讲解:由$n$个物品,进行$m$次染色,求$m$次染色之后,最终物品有哪几种颜色?
1、节点的保存方式:
struct Node_t {
int l, r;
mutable int v;
Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
bool operator<(const Node_t &o) const { return l < o.l; }
};
注意:
-
$l、r、v$ 表示:第 $l$ ~ $r$ 件物品被染成了 $v$ 。
-
mutable 关键字的含义:被 mutable 修饰的变量(mutable 只能用于修饰类中的非静态数据成员),将永远处于可变的状态,即使在一个 const 函数中。
2、$split$ 函数:
$split$ 是最核心的操作之一,它用于将原本包含点 x 的区间(设为 [l, r])分裂为两个区间[l,x)和[x,r]并返回指向后者的迭代器。在进行分裂之前,我们首先要找到$x$所在的线段,由于所有的区间都存储到$set$ 中,于是我们可以借助 $set$ 中的查找函数 $upper$_$bound$ ,其返回的指向是$set$内区间左端点大于$x$的迭代器(简单理解为地址),将其自减得到的就是包含$x$区间的迭代器。接下来就是进行区间分裂,如果此时 $x$ 就是区间的左端点,那我们就不需要进行分裂,直接返回迭代器的位置就行了,如图:
倘若,$x$ 不是左端点该如何处理?那直接删除 $x$ 所在的区间,然后插入区间 $[l,x-1]、[x,r]$ ,那就产生了一个新的问题,我们如何返回 $x$ 所在区间的迭代器?其实 $set$ 的 $insert$ 函数会返回一个 $pair$ 结构体,其中 $pair中的first$ 就是 $x$ 所在位置的迭代器,直接返回即可。
set<Node_t>::iterator split(int x)
{
if (x > n) return odt.end();
auto it = --odt.upper_bound(Node_t{x, 0, 0});
if (it->l == x) return it;
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert(Node_t(l, x - 1, v));
return odt.insert(Node_t(x, r, v)).first;
}
3、$assign$ 函数
操作 $assign$ 用于对一段区间进行赋值。对于ODT来说,区间操作只有这个比较特殊,也是保证复杂度的关键。假设现在我们需要对区间 $[l、r]$ 进行染色,如图:
因此需要将 $L、R$ 与其之前的区间断开,这个时候我们就需要用到 $split$ 函数,将其断开之后,使用$erase$暴力的删除它们之前的这段区间,然后在$set$ 中添加区间$[L、R]$。
注意:
-
由于$erase$删除的区间是前闭后开,所以我们要$split(R+1)$。
-
珂朵莉树在进行求取区间左右端点操作时,必须先 split 右端点,再 split 左端点。若先split左端点,返回的迭代器可能在split右端点的时候失效,可能会导致 RE。
void assign(int l, int r, int v)
{
auto itr = split(r + 1), itl = split(l); //注意要先分裂R+1
odt.erase(itl, itr);
odt.insert(Node_t(l, r, v));
}
4、其它操作:
套模板就好了,参考代码如下:
void performance(int l, int r)
{
auto itr = split(r + 1), itl = split(l);
for (auto it=itl; it != itr; ++it)
{
、、、
}
}
注意:
- 开始的时候,我们需要将全部区间添加进 $set$ 中。
set<Node_t> odt;
odt.insert({1,N,-1});
- 在使用珂朵莉树的时候,往往需要观察一些性质,减少一些其它操作,避免过高的时间复杂度,例如:Physical Education Lessons。
如果你认为你真的理解了珂朵莉树,那么你可以尝试这一题: 数颜色
回到本题,本题和讲解时的样例处理几乎一样,需要处理的就是最后的询问,我们开一个set将全部节点的$v$存进去,返回size-1就行了(初始化的时候插进来的一个大区间不算在结果内)。
完整代码:
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10,INF=0x3f3f3f3f;
#define ll long long
struct Node_t {
int l, r;
mutable int v;
Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}
bool operator<(const Node_t &o) const { return l < o.l; }
};
set<Node_t> odt;
int n;
set<Node_t>::iterator split(int x)
{
if (x > N) return odt.end();
set<Node_t>::iterator it = --odt.upper_bound(Node_t{x, 0, 0});
if (it->l == x) return it;
int l = it->l, r = it->r, v = it->v;
odt.erase(it);
odt.insert(Node_t(l, x - 1, v));
return odt.insert(Node_t(x, r, v)).first;
}
void assign(int l, int r, int v)
{
auto itr = split(r + 1), itl = split(l);
odt.erase(itl, itr);
//也可以在这做一些其它操作
odt.insert(Node_t(l, r, v));
}
//询问有多少张海报
int ask()
{
set<Node_t>::iterator itr = split(N + 1), itl = split(1);
set<int> sum;
for (auto it = itl; it != itr; ++it)
{
sum.insert(it->v);
}
// cout << sum.size() << '\n';
return sum.size()-1;
}
void solve()
{
cin>>n;
odt.insert({1,N,0});
for(int i=1; i<=n; i++)
{
int l,r,v=i;
cin>>l>>r , assign(l,r,v) ;
}
cout << ask() << '\n';
odt.clear();
}
int main()
{
ios::sync_with_stdio(false) , cin.tie(0);
int t; cin>>t;
while(t--) solve();
return 0;
}