珂朵莉树板子，我觉得洛谷题解讲的就很不错
粘一下自己的板子
#include<bits/stdc++.h>
#define re register
#define LL long long
#define ST std::set<node>::iterator
inline int ksm(int a,int b,int mod) {
int S=1;
for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
return S;
}
const int MOD7=1000000007;
struct node {
int l,r;
mutable LL v;
bool operator<(const node &A) const{if(l==A.l) return r<A.r;return l<A.l;}
};
struct Seg{LL v;int t;}a[100005];
inline int cmp(const Seg &A,const Seg &B) {return A.v<B.v;}
std::set<node> s;
int n,m,seed,vmax;
inline int rnd() {
int ret=seed;
seed=(seed*7ll+13)%MOD7;
return ret;
}
inline ST split(int pos) {
ST it=s.lower_bound((node){pos,-1,0});
if(it!=s.end()&&it->l==pos) return it;
--it;
int L=it->l,R=it->r;LL t=it->v;
s.erase(it);
s.insert((node){L,pos-1,t});
return s.insert((node){pos,R,t}).first;
}
inline void pia(int l,int r,int v) {
ST itl=split(l),itr=split(r+1);
s.erase(itl,itr);
s.insert((node){l,r,(LL)v});
}
inline void add(int l,int r,int t) {
ST itl=split(l),itr=split(r+1);
for(;itl!=itr;++itl) itl->v+=t;
}
inline int calc(int l,int r,int x,int mod) {
ST itl=split(l),itr=split(r+1);
int ans=0;
for(;itl!=itr;++itl)
ans=(ans+1ll*ksm(itl->v%mod,x,mod)*(itl->r-itl->l+1)%mod)%mod;
return ans;
}
inline LL rk(int l,int r,int k) {
ST itl=split(l),itr=split(r+1);
int cnt=0;
for(;itl!=itr;++itl) a[++cnt].v=itl->v,a[cnt].t=itl->r-itl->l+1;
std::sort(a+1,a+cnt+1,cmp);
for(re int i=1;i<=cnt;i++) {
if(k-a[i].t>0) {k-=a[i].t;continue;}
return a[i].v;
}
}
int main() {
//scanf("%d%d%lld%lld",&n,&m,&seed,&vmax);
std::cin>>n>>m>>seed>>vmax;
for(re int i=1;i<=n;i++) s.insert((node){i,i,rnd()%vmax+1});
int op,l,r,x,y;
for(re int i=1;i<=m;i++) {
op=rnd()%4+1;
l=rnd()%n+1;r=rnd()%n+1;
if(l>r) std::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==1) add(l,r,x);
if(op==2) pia(l,r,x);
if(op==4) printf("%d
",calc(l,r,x,y));
if(op==3) std::cout<<rk(l,r,x),putchar(10);
}
return 0;
}