#include<cstdio>
#include<set>
#include<algorithm>
#define in inline
#define re register
#define int long long
#define It set<node>::iterator
using namespace std;
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
const int size=100005;
int n,m,seed,yyb,a[size];
in int rnd()
{
int ret=seed;
seed=(seed*7+13)%1000000007;
return ret;
}
struct node{
int l,r;
mutable int v;//mutable关键字让v可修改, 否则修改const变量会CE
node(int L,int R,int V){l=L,r=R,v=V;}
bool operator<(const node &t)const{return l<t.l;}//STLset和priority_queue中重载运算符都要注意加const, 否则CE
};
set<node> s;
in It split(int p)//以p为界分割区间, 返回指向p所在区间的迭代器
{
It it=s.lower_bound(node{p,0,0});
if(it!=s.end()&&it->l==p) return it;//不需要分割区间
--it;
int L=it->l,R=it->r,V=it->v;
s.erase(it);
s.insert(node{L,p-1,V});
return s.insert(node{p,R,V}).first;
}
in void assign_v(int l,int r,int v)
{
It itr=split(r+1),itl=split(l);//注意先割右端点再割左端点, 假如先割左端点, 再割右端点时itl就失效了
s.erase(itl,itr);//delete[itl,itr), 由于不包括itr, 所以我们之前要split(r+1)
s.insert(node{l,r,v});
}
in void add(int l,int r,int v)
{
It itr=split(r+1);
for(It it=split(l);it!=itr;++it) it->v+=v;
}
struct data{int v,len;bool operator<(const data&t){return v<t.v;}}d[size];
in int rankk(int l,int r,int k)
{
It itr=split(r+1);int cnt=0;
for(It it=split(l);it!=itr;++it)
d[++cnt].v=it->v,d[cnt].len=it->r-it->l+1;
sort(d+1,d+cnt+1);
for(re int i=1;i<=cnt;++i)
{
k-=d[i].len;
if(k<=0) return d[i].v;
}
}
in int ksm(int ba,int k,int mod)
{
int ans=1;ba%=mod;
while(k)
{
if(k&1) ans=ans*ba%mod;
k>>=1;
ba=ba*ba%mod;
}
return ans;
}
in int msum(int l,int r,int zs,int mod)
{
It itr=split(r+1);
int ans=0;
for(It it=split(l);it!=itr;++it)
ans=(ans+(it->r-it->l+1)%mod*ksm(it->v,zs,mod))%mod;//注意乘上区间长度
return ans;
}
signed main()
{
n=read(),m=read(),seed=read(),yyb=read();
for(re int i=1;i<=n;++i) a[i]=rnd()%yyb+1;
for(re int i=1;i<=n;++i) s.insert(node{i,i,a[i]});
for(re int i=1;i<=m;++i)
{
int op=rnd()%4+1,l=rnd()%n+1,r=rnd()%n+1,x,y;
if(l>r) l^=r,r^=l,l^=r;
if(op==3) x=rnd()%(r-l+1)+1;
else x=rnd()%yyb+1;
if(op==4) y=rnd()%yyb+1;
if(op==1) add(l,r,x);
if(op==2) assign_v(l,r,x);
if(op==3) printf("%lld\n",rankk(l,r,x));
if(op==4) printf("%lld\n",msum(l,r,x,y));
}
return 0;
}
最新评论