题目

珂朵莉树板子，我觉得洛谷题解讲的就很不错

粘一下自己的板子

#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\n",calc(l,r,x,y));
        if(op==3) std::cout<<rk(l,r,x),putchar(10);
    }
    return 0;
}