珂朵莉树(ODT)
热度: loading...
一、什么是珂朵莉树
珂朵莉(抱走~~)树，又称Old Driver Tree(ODT)。这是一种能暴力解决数据结构问题的数据结构。（（
二、什么时候用珂朵莉树
关键操作：推平一段区间，使一整段区间内的东西变得一样。保证数据随机。
当然，一些线段树的问题也可以用它做，只不过分数嘛，嘿嘿。
三、珂朵莉树的操作
①初始化
struct node//先定义一个结构体
{
int l,r;
mutable ll v;//不管是什么类型，一定要注意加上mutable!
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维护这个数据结构
set<node> s;
s.insert(L,R,V)//插入
②核心操作，分离：Split
#define IT set<node>::iterator
IT Split(int pos)
{
IT pl=s.lower_bound(node(pos));//找到首个pl不小于pos的节点。
if(pl!=s.end()&&pl->l==pos)return pl;//如果无需分离，直接返回
pl--;//否则pos所在区间一定在pl-1里
int L=pl->l,R=pl->r;ll V=pl->v;//指针!
s.erase(pl);
s.insert(node(L,pos-1,V));//插入
return s.insert(node(pos,R,V)).first;//返回后半段的迭代器
}
将pos所在区域(假如为[L,R])分为[L,pos-1]与[pos,R]两个区间
注意一定要用set
③推平操作：Assign
void Ass(int L,int R,ll x=0)//若x没有被赋予初值，则x=1
{
IT p_r=Split(R+1),p_l=Split(L);
s.erase(p_l,p_r);//清空set中第p_l到第p_r个区间
s.insert(node(L,R,x));
}
将[L,R]区间的所有数变为x
④区间加法：Add
void add(int L,int R,ll x=1)
{
IT p_r=Split(R+1),p_l=Split(L);
for (;p_l!=p_r;p_l++)
p_l->v+=x;
}
⑤区间第k小：Rank
ll Rank_k(int L,int R,int k)
{
vector<pair<ll,int> > pl;
IT p_r=Split(R+1),p_l=Split(L);
for (;p_l!=p_r;p_l++)
pl.push_back(pair<ll,int>(p_l->v,p_l->r-p_l->l+1));
sort(pl.begin(),pl.end());
for(vector<pair<ll,int> >::iterator it=pl.begin();it!=pl.end();it++)
{
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}
这里用一个vector维护数列
不断地减，直到刚好小于零时，此时一定为第k值
⑥区间k次幂的和：Sum
ll sum(int L,int R,int x,int M)//模数M
{
IT p_r=Split(R+1),p_l=Split(L);
ll res=0;
for (;p_l!=p_r;p_l++)
res=(res+(ll)(p_l->r-p_l->l+1)*ksm(p_l->v,x,M))%M;
return (res+M)%M;
}
若要看例题，点击：CF896C
完整代码(例题)：
#include<bits/stdc++.h>
#define FQ(i,a,b) for(register int i=a;i<=b;i++)
#define prf printf
#define scf scanf
#define ll long long
#define IT set<node>::iterator //important
using namespace std;
const int N=1e5+10,M_0=1e9+7;
ll a[N],seed,n,m,V_max;
ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll ksm(ll x,ll y,ll M)
{
ll res=1;x%=M;
while(y)
{
if(y&1)res=(res*x)%M;
x=(x*x)%M;
y>>=1;
}
return res;
}
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> s;
IT Split(int pos)//分离
{
IT pl=s.lower_bound(node(pos));
if(pl!=s.end()&&pl->l==pos)return pl;
pl--;
int L=pl->l,R=pl->r;ll V=pl->v;
s.erase(pl);
s.insert(node(L,pos-1,V));
return s.insert(node(pos,R,V)).first;
}
void Ass(int L,int R,ll x=0)//推平
{
IT p_r=Split(R+1),p_l=Split(L);
s.erase(p_l,p_r);
s.insert(node(L,R,x));
}
ll sum(int L,int R,int x,int M)//区间k次和
{
IT p_r=Split(R+1),p_l=Split(L);
ll res=0;
for (;p_l!=p_r;p_l++)
res=(res+(ll)(p_l->r-p_l->l+1)*ksm(p_l->v,x,M))%M;
return (res+M)%M;
}
void add(int L,int R,ll x=1)//区间加法
{
IT p_r=Split(R+1),p_l=Split(L);
for (;p_l!=p_r;p_l++)
p_l->v+=x;
}
ll Rank_k(int L,int R,int k)
{
vector<pair<ll,int> > pl;
IT p_r=Split(R+1),p_l=Split(L);
for (;p_l!=p_r;p_l++)
pl.push_back(pair<ll,int>(p_l->v,p_l->r-p_l->l+1));
sort(pl.begin(),pl.end());
for(vector<pair<ll,int> >::iterator it=pl.begin();it!=pl.end();it++)
{
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}
ll rnd()
{
ll ret=seed;
seed=(seed*7+13)%M_0;
return ret;
}
int main()
{
n=read(),m=read(),seed=read(),V_max=read();
for(int i=1;i<=n;i++)
{
a[i]=(rnd()%V_max)+1;
s.insert(node(i,i,a[i]));
}
for(int i=1,x,y;i<=m;i++)
{
int opt=int(rnd()%4)+1;
int l=int(rnd()%n)+1,r=int(rnd()%n)+1;
if(l>r)swap(l,r);
if(opt==3)x=int(rnd()%(r-l+1))+1;
else x=int(rnd()%V_max)+1;
if(opt==4)y=int(rnd()%V_max)+1;
if(opt==1)add(l,r,(ll)x);
if(opt==2)Ass(l,r,(ll)x);
if(opt==3)printf("%lld\n",Rank_k(l,r,x));
if(opt==4)printf("%lld\n",sum(l,r,x,y));
}
return 0;
}
//**月雩·薇嫭**
