题目
支持区间加，区间推平，询问区间第\(k\)小，
以及询问区间\(\sum{a_i^x}\pmod y\)，数据随机
分析
由于数据随机，那么区间推平的概率为\(\frac{1}{4}\)，
考虑用珂朵莉树实现，用\(STL::set\)装下相同元素段，
对于取出一段区间，分离左右端点，直接修改即可
代码
#include <cstdio>
#include <cctype>
#include <set>
#include <algorithm>
#define rr register
using namespace std;
typedef long long lll;
struct rec{
int l,r; mutable lll w;
inline bool operator <(const rec &t)const{
return l<t.l;
}
};
struct Two{
lll w; int len;
inline bool operator <(const Two &t)const{
return w<t.w;
}
}b[100011];
typedef set<rec>::iterator ir; ir it0,it1,it;
set<rec>K; int n,m,seed,mx,mod;
inline void print(lll ans){
if (ans>9) print(ans/10);
putchar(ans%10+48);
}
inline signed Get(){
rr int ans=seed;
seed=(7ll*seed+13)%1000000007;
return ans;
}
inline lll ksm(lll x,lll y,lll p){
rr lll ans=1;
for (;y;y>>=1,x=x*x%p)
if (y&1) ans=ans*x%p;
return ans;
}
inline ir Split(int x){
it=K.lower_bound((rec){x,0,0});
if (it!=K.end()&&it->l==x) return it;
rr rec t=*(--it); K.erase(it);
K.insert((rec){t.l,x-1,t.w});
return K.insert((rec){x,t.r,t.w}).first;
}
inline void Assign(int l,int r,int w){
it1=Split(r+1),it0=Split(l);
K.erase(it0,it1);
K.insert((rec){l,r,w});
}
signed main(){
scanf("%d%d%d%d",&n,&m,&seed,&mx);
for (rr int i=1;i<=n;++i)
K.insert((rec){i,i,Get()%mx+1});
K.insert((rec){n+1,n+1,0});
for (rr int i=1;i<=m;++i){
rr int opt=Get()%4+1,l=Get()%n+1,r=Get()%n+1;
if (l>r) l^=r,r^=l,l^=r;
switch (opt){
case 1:{
rr int x=Get()%mx+1;
it1=Split(r+1),it0=Split(l);
for (;it0!=it1;++it0) it0->w+=x;
break;
}
case 2:{
rr int x=Get()%mx+1;
Assign(l,r,x);
break;
}
case 3:{
rr int kth=Get()%(r-l+1)+1,tot=0;
it1=Split(r+1),it0=Split(l);
for (;it0!=it1;++it0){
rr rec t=*it0;
b[++tot]=(Two){t.w,t.r-t.l+1};
}
sort(b+1,b+1+tot);
for (rr int i=1;i<=tot;++i){
kth-=b[i].len;
if (kth<=0) {print(b[i].w),putchar(10); break;}
}
break;
}
case 4:{
rr int y=Get()%mx+1,mod=Get()%mx+1; rr lll ans=0;
it1=Split(r+1),it0=Split(l);
for (;it0!=it1;++it0){
rr rec t=*it0;
ans=(ans+ksm(t.w,y,mod)*(t.r-t.l+1)%mod)%mod;
}
print(ans),putchar(10);
break;
}
}
}
return 0;
}