处理区间赋值问题的神器！
珂朵莉树的实现非常简单（baoli）,建树时把区间的左右端点和权值作为一个节点 全扔到std::set（或者链表）中维护即可
split: 核心操作之一,将一段区间提取出来，在此之上进行一些操作
assign: 核心操作之二，也是降低珂朵莉树时间复杂度的重要操作，把一段区间推平赋值，减少大量节点个数，防止其退化成暴力
其他操作就非常暴力的进行就可以了
在网上查珂朵莉的时间复杂度大概是 \(n \log \log\) 的，常数很小，在随机数据下吊打线段树
但是，很多毒瘤的出题人会卡珂朵莉树，让区间赋值操作尽可能的少，这样就寄了
以这道题为例 CF896C （珂朵莉树起源）
大体操作：区间加 区间修改 求区间第k小 求区间x次幂
$my\,\ code$
#include<bits/stdc++.h>
#define read(a) scanf("%lld",&a)
#define read4(a,b,c,d) scanf("%lld%lld%lld%lld",&a,&b,&c,&d)
#define write(a) printf("%lld\n",a)
#define mem(a) memset(a,0,sizeof(a));
#define debug() puts("qwq qwq qwq qwq qwq");
#define Chtholly set <node>::iterator
using namespace std;
constexpr int N(1e5+5);
#define int long long
int n,m,seed,vmax,a[N];
inline int rnd(){
int ret=seed;
seed=(seed*7+13)%1000000007;
return ret;
}
inline void make_data(int &op,int &l,int &r,int &x,int &y){
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;
}
struct node{
int l,r;mutable int v;
node()=default;
node(int L,int R=0,int V=0):l(L),r(R),v(V){}
bool operator<(const node &x)const{return l<x.l;}
};
set <node> odt;
Chtholly split(int pos){
auto it=odt.lower_bound(pos);
if(it!=odt.end()&&it->l==pos) return it;
--it;if(it->r<pos) return odt.end();
int l=it->l,r=it->r,v=it->v;
odt.erase(it);odt.insert(node(l,pos-1,v));
return odt.insert(node(pos,r,v)).first;
}
inline void assign(int l,int r,int v){
auto it2=split(r+1),it1=split(l);
odt.erase(it1,it2);
odt.insert(node(l,r,v));
}
inline void add(int l,int r,int v){
auto it2=split(r+1),it1=split(l);
for(;it1!=it2;++it1){it1->v+=v;}
}
inline int kth(int l,int r,int k){
auto it2=split(r+1),it1=split(l);
vector <pair<int,int>> g;
vector <pair<int,int>>().swap(g);
for(;it1!=it2;++it1)
g.push_back(make_pair(it1->v,it1->r-it1->l+1));
sort(g.begin(),g.end());
for(auto i:g){
k-=i.second;
if(k<=0) return i.first;
}
return -1;
}
inline int qpow(int a,int b,int p){
int ret(1);a%=p;
for(;b;a=a*a%p,b>>=1)
if(b&1) ret=ret*a%p;
return ret;
}
inline int sum(int l,int r,int x,int y){
auto it2=split(r+1),it1=split(l);
int ret(0);
for(;it1!=it2;++it1)
ret=(ret+qpow(it1->v,x,y)*(it1->r-it1->l+1)%y)%y;
return ret;
}
signed main(){
read4(n,m,seed,vmax);
for(int i=1;i<=n;++i) a[i]=(rnd()%vmax)+1,odt.insert(node(i,i,a[i]));
for(int i=1,op,l,r,x,y;i<=m;++i){
make_data(op,l,r,x,y);
switch(op){
case 1:add(l,r,x);break;
case 2:assign(l,r,x);break;
case 3:write(kth(l,r,x));break;
case 4:write(sum(l,r,x,y));break;
}
}
return 0;
}