【Study】ODT

如何理解每一个节点呢？

假设有这么一段数列

1 1 1 1 4 4 3

那么我们就会构建三个节点，分别如下：

id:1 -> l=1 r=4 v=1
id:2 -> l=5 r=6 v=4
id:3 -> l=7 r=7 v=3

但是在一开始输入初始数组时，我们仅需对于每一个值建立一个节点，相同值的合并可以留到后面的操作来处理。

下面要注意有一个点，这里有个 mutable ，由于在 \(set\) 中，元素是以常量方式储存的，我们无法对其直接进行修改，因为 \(set\) 里面元素的排列顺序是个根据 \(l\) 的大小，与 \(v\) 无关，所以我们可以加个 mutable 来直接修改 \(v\) ，否则就要先删除元素再插入元素，降低了效率。

接着再

set odt;

就行了

2、\(Slpit\) 操作

这是 \(ODT\) 的核心操作之一，当某处需要修改时，发现这一处包含在一个节点之内，如何处理？我们就需要将这个节点拆成两部分。

假如我们 \(Split(i)\) ，且 \(i\) 包含在区间 \([l,r]\) 中，那么执行 \(Split\) 操作之后这个区间就会分为 \([l,i-1]\) 和 \([i,r]\) 这两个区间，接着就可以愉快地进行修改或查询了。

#define iter set::iterator
iter Split(int x)
//注意我们返回的是一个迭代器方便查找修改
{
	if(x>n) return odt.end();
    //如果查询的位置大于n就不必分裂

	iter it=--odt.upper_bound(node(x));
    //找到包含x的区间，即找到包含x的区间的左端点

	if(it->l==x) return it;
    //为左端点不必分裂

	int l=it->l,r=it->r,v=it->v;
    //先将节点的信息取出来
	odt.erase(it);
    //删掉节点

	odt.insert(node(l,x-1,v));
    //插入前半段[l,x-1],值为v
	return odt.insert(node(x,r,v)).first;
    //插入后半段，再返回后半段的迭代器
}

3、\(assign\) 操作

这也是 \(ODT\) 的核心操作之一，是实现区间合并的主要操作

void Assign(int l,int r,int v)
//将区间[l,r]都改为v且保存到一个节点
{
	iter itr=Split(r+1),itl=Split(l);
    //找出修改区间的起点和终点
	odt.erase(itl,itr);
    //删除区间[l,r+1)
	odt.insert(node(l,r,v));
    //插入节点
}

这里有个细节，对于分裂区间 \([l,r+1)\) 要先执行 Split(r+1) ，再执行 Split(l)

假如 \(l\) 和 \(r\) 均包含在区间 \([L,R]\) 。

我们先 Split(l) ，那么某段区间就会分解为 \([L,l-1]\) 和 \([l,R]\) ，并且返回 \([l,R]\) 的迭代器；

接着 Split(r+1) ，这时就会将 \([l,R]\) 分解为 \([l,r-1]\) 和 \([r,R]\) ，并且删除 \([l,R]\) 的迭代器，第一次返回的迭代器被删除了，这时就会导致 \(Re\)

所以切记，先执行 Split(r+1) ，再执行 Split(l) qwq

3、其他操作

区间加

分裂后直接暴力（

#define iter set::iterator
void add(int l,int r,int val)
{
	iter itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl) 
        itl->v+=val;
}

区间第 \(k\) 小

取出区间直接 \(sort\) (

#define iter set::iterator
struct Rank{
	int num,cnt;
	Rank(int _num,int _cnt){num=_num;cnt=_cnt;}
	bool operator < (const Rank &a) const {return num ve;
	for(;itl!=itr;++itl) 
        ve.push_back(Rank(itl->v,itl->r - itl->l + 1));
	sort(ve.begin(),ve.end());
	int i=0;
	for(;i

#define iter set::iterator
int askpower(int l,int r,int b,int p)
{
	iter itr=split(r+1),itl=split(l);
	int ans=0;
	for(;itl!=itr;++itl) 
		ans+=(Power(itl->v,b,p)*(itl->r - itl->l + 1)%p),ans%=p;
	return ans;
}
//Power(a,b,p)为快速幂，求a^b%p

#define iter set::iterator
void qwq(int l,int r,...)
{
    iter itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
    {
        ...
        //一通乱搞（
    }
}