月雩の小窝(损坏)
 
Made by 月雩 禁止转载(作者允许除外) | Theme: Fog
载入天数...
载入时分秒...
总访问量:  |   访问人数:
Copyright © 2020 pray-yueyu.github.io

珂朵莉树(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::iterator(NOI及NOIP不能用auto)

③推平操作: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;	
	
} 
//**月雩·薇嫭**