[CF896C]Willem, Chtholly and Seniorious[ODT]

#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;
}