登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.10 珂朵莉树 › 珂朵莉树 / 搜索
JSON MD

2.10 珂朵莉树

珂朵莉树 optimize
81 行
CPP JSON
【珂朵莉树】 代码包含 rnd, mi, split, assign, add 等核心函数,实现了 珂朵莉树 的算法逻辑。 核心函数: int rnd(无参数) — 核心算法函数 LL mi(LL a,LL k,LL P) — 核心算法函数 IT split(Re w) — 分裂操作 void assign(Re l,Re r,LL v) — 核心算法函数 void add(Re l,Re r,LL v) — 加法更新 LL mi_sum(Re l,Re r,Re k,Re P) — 核心算法函数 LL ask_k(Re l,Re r,Re k) — 核心算法函数 核心结构体:QAQ 关键配置: N=1e5+5
C++ 80 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define LL long long
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+5;
struct QAQ{
	int l,r;mutable LL v;
	QAQ(int L,int R=-1,LL V=0):l(L),r(R),v(V){}
	bool operator<(QAQ o)const{return l<o.l;}
};
int l,r,x,y,n,m,fu,op,seed,vmax,a[N];set<QAQ>s;
inline int rnd(){
    Re tmp=seed;
    seed=((LL)seed*7+13)%1000000007;
    return tmp;
}
inline LL mi(LL a,LL k,LL P){
	LL ans=1;a%=P;
	while(k){
		if(k&1)(ans*=a)%=P;
		(a*=a)%=P,k>>=1;
	}
	return ans;
}
inline IT split(Re w){
	IT it=s.lower_bound(QAQ(w));
	if(it!=s.end()&&it->l==w)return it;
	--it;
	Re L=it->l,R=it->r;LL V=it->v;
	s.erase(it);
	s.insert(QAQ(L,w-1,V));
	return s.insert(QAQ(w,R,V)).first;
}
inline void assign(Re l,Re r,LL v){
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr),s.insert(QAQ(l,r,v));
}
inline void add(Re l,Re r,LL v){
	IT itr=split(r+1),itl=split(l);
	while(itl!=itr)itl->v+=v,++itl;
}
inline LL mi_sum(Re l,Re r,Re k,Re P){
	IT itr=split(r+1),itl=split(l);LL ans=0;
	while(itl!=itr)(ans+=(LL)(itl->r-itl->l+1)%P*mi(itl->v,(LL)k,(LL)P)%P)%=P,++itl;
	return ans;
}
inline LL ask_k(Re l,Re r,Re k){
	IT itr=split(r+1),itl=split(l);
	vector<pair<LL,int> >Q;
	Q.clear();
	while(itl!=itr)Q.push_back(pair<LL,int>(itl->v,itl->r-itl->l+1)),++itl;
	sort(Q.begin(),Q.end());
	for(vector<pair<LL,int> >::iterator it=Q.begin();it!=Q.end();++it){
		k-=it->second;
		if(k<=0)return it->first;
	}
}
int main(){
	scanf("%d%d%d%d",&n,&m,&seed,&vmax);
	for(Re i=1;i<=n;++i)a[i]=(rnd()%vmax)+1,s.insert(QAQ(i,i,a[i]));
	s.insert(QAQ(n+1,n+1,0));
	while(m--){
	    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;
	    
	    if(op<2)add(l,r,(LL)x);
		else if(op<3)assign(l,r,(LL)x);
		else if(op<4)printf("%lld\n",ask_k(l,r,x));
		else printf("%lld\n",mi_sum(l,r,x,y));
	}
}
序列操作 P2572
67 行
CPP JSON
【序列操作(P2572)】 代码包含 in, split, assign, count1, ask1 等核心函数,实现了 序列操作 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 IT split(Re w) — 分裂操作 void assign(Re l,Re r,Re v) — 核心算法函数 int count1(Re l,Re r) — 核心算法函数 int ask1(Re l,Re r) — 核心算法函数 void inverse(Re l,Re r) — 求模逆元 核心结构体:QAQ 关键配置: N=1e5+5
C++ 66 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=1e5+5;
struct QAQ{
    int l,r;mutable int v;
    QAQ(Re L,Re R=-1,Re V=0):l(L),r(R),v(V){}
    bool operator<(QAQ o)const{return l<o.l;}
};
int x,y,n,m,fu,op;set<QAQ>s;
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(fu)x=-x;
}
inline IT split(Re w){
    IT it=s.lower_bound(QAQ(w));
    if(it!=s.end()&&it->l==w)return it;
    --it;
    Re L=it->l,R=it->r,V=it->v;
    s.erase(it);
    s.insert(QAQ(L,w-1,V));
    return s.insert(QAQ(w,R,V)).first;
}
inline void assign(Re l,Re r,Re v){
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr),s.insert(QAQ(l,r,v));
}
inline int count1(Re l,Re r){
	IT itr=split(r+1),itl=split(l);Re ans=0;
	while(itl!=itr)ans+=itl->v*(itl->r-itl->l+1),++itl;
	return ans;
}
inline int ask1(Re l,Re r){
	IT itr=split(r+1),itl=split(l);Re tmp=0,ans=0;
	while(itl!=itr){
		if(itl->v)tmp+=itl->r-itl->l+1;
		else ans=max(ans,tmp),tmp=0;
		++itl;
	}
	return max(ans,tmp);
}
inline void inverse(Re l,Re r){
	IT itr=split(r+1),itl=split(l);
	while(itl!=itr)itl->v^=1,++itl;
}
int main(){
    in(n),in(m);
    for(Re i=1;i<=n;++i)in(x),s.insert(QAQ(i,i,x));
    s.insert(QAQ(n+1,n+1,-1));
    while(m--){
        in(op),in(x),in(y);++x,++y;
        if(!op)assign(x,y,0);
        else if(op<2)assign(x,y,1);
        else if(op<3)inverse(x,y);
        else if(op<4)printf("%d\n",count1(x,y));
        else printf("%d\n",ask1(x,y));
    }
}
脑洞治疗仪 optimize
69 行
CPP JSON
【脑洞治疗仪】 代码包含 in, split, assign, ask1, scure 等核心函数,实现了 脑洞治疗仪 的算法逻辑。 核心函数: void in(Re &x) — 核心算法函数 IT split(Re w) — 分裂操作 void assign(Re l,Re r,Re v) — 核心算法函数 int ask1(Re l,Re r) — 核心算法函数 void scure(Re l,Re r,Re a,Re b) — 核心算法函数 核心结构体:QAQ 关键配置: N=2e5+5
C++ 68 行 CPP
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<vector>
#include<set>
#define Re register int
#define IT set<QAQ>::iterator
using namespace std;
const int N=2e5+5;
struct QAQ{
    int l,r;mutable int v;
    QAQ(Re L,Re R=-1,Re V=0):l(L),r(R),v(V){}
    bool operator<(QAQ o)const{return l<o.l;}
};
int x,y,xx,yy,n,m,fu,op;set<QAQ>s;
inline void in(Re &x){
    x=fu=0;char c=getchar();
    while(c<'0'||c>'9')fu|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(fu)x=-x;
}
inline IT split(Re w){
    IT it=s.lower_bound(QAQ(w));
    if(it!=s.end()&&it->l==w)return it;
    --it;
    Re L=it->l,R=it->r,V=it->v;
    s.erase(it);
    s.insert(QAQ(L,w-1,V));
    return s.insert(QAQ(w,R,V)).first;
}
inline void assign(Re l,Re r,Re v){
    IT itr=split(r+1),itl=split(l);
    s.erase(itl,itr),s.insert(QAQ(l,r,v));
}
inline int ask1(Re l,Re r){
	IT itr=split(r+1),itl=split(l);Re tmp=0,ans=0;
	while(itl!=itr){
		if(!itl->v)tmp+=itl->r-itl->l+1;
		else ans=max(ans,tmp),tmp=0;
		++itl;
	}
	return max(ans,tmp);
}
inline void scure(Re l,Re r,Re a,Re b){
	IT itr=split(r+1),itl=split(l),it=itl;Re t=0;
	while(it!=itr)t+=it->v*(it->r-it->l+1),++it;
	s.erase(itl,itr),s.insert(QAQ(l,r,0));
	if(!t)return;
	itr=split(b+1),itl=split(a);
	if(t>=b-a+1){s.erase(itl,itr),s.insert(QAQ(a,b,1));return;}
	for(;itl!=itr;++itl)
		if(!itl->v){
			t-=itl->r-itl->l+1;
			if(t<0){assign(itl->l,itl->r+t,1);break;}
			else itl->v=1;
		}
}
int main(){
    in(n),in(m);
    s.insert(QAQ(1,n,1));
    while(m--){
        in(op),in(x),in(y);
        if(!op)assign(x,y,0);
        else if(op<2)in(xx),in(yy),scure(x,y,xx,yy);
        else printf("%d\n",ask1(x,y));
    }
}
已复制