珂朵莉树（ODT）

把值相同的区间合并成一个结点保存在 set 里面。

参考资料

实现

保存结点

struct Node
{
	int l,r;
	mutable ll v;
	bool operator<(const Node &rhs) const{return l<rhs.l;}
};
set<Node> s;

insert

s.insert({l,r,v});

split

把包含 $x$ 的区间 $[l,r]$ 区间分裂成 $[l,x-1]$ 和 $[x,r]$ ，并返回 $[x,r]$ 的迭代器。

auto split(int x)
{
	auto it=s.lower_bound({x,0,0});
	if(it!=s.end()&&it->l==x)return it;
	it--;
	auto [l,r,v]=*it;
	s.erase(it);
	s.insert({l,x-1,v});
	return s.insert({x,r,v}).first;
}

注意

珂朵莉树在进行求取区间左右端点操作时，必须先 split 右端点，再 split 左端点。

若先 split 左端点，返回的迭代器可能在 split 右端点的时候失效，可能会导致 RE。

cover

void cover(int l,int r,ll v)
{
	auto it2=split(r+1),it1=split(l);
	s.erase(it1,it2);
	s.insert({l,r,v});
}

add

void add(int l,int r,ll v)
{
	auto it2=split(r+1),it1=split(l);
	for(auto it=it1;it!=it2;it++)it->v+=v;
}

sum

ll sum(int l,int r)
{
	auto it2=split(r+1),it1=split(l);
	ll res=0;
	for(auto it=it1;it!=it2;it++)res+=it->v*(it->r-it->l+1);
	return res;
}

例题

洛谷 CF896C Willem, Chtholly and Seniorious

请你写一种奇怪的数据结构，支持 $4$ 种操作：

1 l r x：将 $[l,r]$ 区间所有数加上 $x$ 。
2 l r x：将 $[l,r]$ 区间所有数改成 $x$ 。
3 l r x：求 $[l,r]$ 区间的第 $x$ 小。
4 l r x y：求 $[l,r]$ 区间每个数字的 $x$ 次方的和对 $y$ 取模的值。

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
ll Pow(ll a,ll b,ll mod)
{
	a%=mod;
	ll res=1;
	while(b)
	{
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
struct Node
{
	int l,r;
	mutable ll v;
	bool operator<(const Node &rhs) const{return l<rhs.l;}
};
set<Node> s;
auto split(int x)
{
	auto it=s.lower_bound({x,0,0});
	if(it!=s.end()&&it->l==x)return it;
	it--;
	auto [l,r,v]=*it;
	s.erase(it);
	s.insert({l,x-1,v});
	return s.insert({x,r,v}).first;
}
void cover(int l,int r,ll v)
{
	auto it2=split(r+1),it1=split(l);
	s.erase(it1,it2);
	s.insert({l,r,v});
}
void add(int l,int r,ll v)
{
	auto it2=split(r+1),it1=split(l);
	for(auto it=it1;it!=it2;it++)it->v+=v;
}
ll kth(int l,int r,int k)
{
	auto it2=split(r+1),it1=split(l);
	vector<pair<ll,int>> tmp;
	for(auto it=it1;it!=it2;it++)tmp.push_back({it->v,it->r-it->l+1});
	sort(tmp.begin(),tmp.end());
	for(auto it=tmp.begin();it!=tmp.end();it++)
	{
		if(k<=it->second)return it->first;
		k-=it->second;
	}
	return -1;
}
ll query(int l,int r,int x,int mod)
{
	auto it2=split(r+1),it1=split(l);
	ll res=0;
	for(auto it=it1;it!=it2;it++)res=(res+Pow(it->v,x,mod)*(it->r-it->l+1)%mod)%mod;
	return res%mod;
}
int n,m,seed,vmax;
int op,l,r,x,y;
int rnd()
{
	int ret=seed;
	seed=(seed*7ll+13)%1000000007;
	return ret;
}
void init()
{
	op=rnd()%4+1;
	l=rnd()%n+1;
	r=rnd()%n+1;
	if(l>r)swap(l,r);
	if(op==3)x=rnd()%(r-l+1)+1;
	else x=rnd()%vmax+1;
	if(op==4)y=rnd()%vmax+1;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>n>>m>>seed>>vmax;
	for(int i=1;i<=n;i++)s.insert({i,i,rnd()%vmax+1});
	while(m--)
	{
		init();
		if(op==1)add(l,r,x);
		if(op==2)cover(l,r,x);
		if(op==3)cout<<kth(l,r,x)<<'\n';
		if(op==4)cout<<query(l,r,x,y)<<'\n';
	}
	return 0;
}

参考资料​

实现​

保存结点​

insert​

split​

cover​

add​

sum​

例题​

洛谷 CF896C Willem, Chtholly and Seniorious​