odt 珂朵莉树

要保证数据随机化
操作1 ：区间加
操作2 ：区间赋值
操作3 ：区间和
操作4 ： 区间幂次和

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<vector>
#include<queue>
#include<stack>
#include<iostream>
#include<sstream>
#include<set>
#define x first
#define y second
#define lson u<<1
#define rson u<<1|1
#define pb push_back
#define pu pushup
#define mk make_pair
using namespace std;
#define ll long long
inline int read(){
   
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
   if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
#define int long long
struct node{
   
	int l;
	int r;
	mutable  int val;
	// node(int L=-1,int R=-1,int Val=-1)
	// {
   
	// l=L,r=R,val=Val;
	// }
	bool operator <(const node&W)const
	{
   
		return l<W.l;
	}
};
namespace Qpow{
   
	long long pow(long long a, long long b, long long mod){
   
		if (!a) return 0;
		long long res = 1; a %= mod;
		for ( ; b; (a *= a) %= mod, b >>= 1ll)
			if (b & 1) (res *= a) %= mod;;
		return res;
	}
};
int qmi(int a,int b,int c)
{
   
	//printf("c=%lld\n",c);
	//if(!a) return 0;
	if(!a)
		return 0;
	long long res = 1; a %= c;
		for ( ; b; (a *= a) %= c, b >>= 1ll)
			if (b & 1) (res *= a) %= c;
		return res;
}
int n,m,seed,vmax;
int a[100010];
int rnd(){
   
	int ret=seed;
	seed=(seed*7+13)%1000000007;
	return ret;
}
set<node>s;
//#define set <node>::iterator it
set<node>::iterator split(int pos){
   //将它分裂成 [l,pos)[pos,r]
	set<node>::iterator it=s.lower_bound({
   pos,-1,-1});
	if(it!=s.end() && pos==it->l)
		return it;
	it--;
	int l=it->l;
	int r=it->r;
	int val=it->val;
	s.erase(it);
	s.insert({
   l,pos-1,val});
	return s.insert({
   pos,r,val}).first;
}
void assign(int l,int r,int val)
{
   
	set<node>::iterator itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert({
   l,r,val});
}
void add(int l,int r,int val)
{
   
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl;it!=itr;it++)
	{
   
		it->val+=val;
	}
}
int qr(int l,int r,int x,int mod)
{
   
	int res=0;
	set<node>::iterator itr=split(r+1),itl=split(l);
	for(set<node>::iterator it=itl;it!=itr;it++)
	{
   
		res=(res+(it->r-it->l+1)*Qpow::pow(it->val,x,mod))%mod;
	}
	return res;
}
int kth(int l,int r,int k)
{
   
	set<node>::iterator itr=split(r+1),itl=split(l);
	vector<pair<int,int>>v(0);
	for(set<node>::iterator it=itl;it!=itr;it++)
	{
   
			v.push_back({
   it->val,it->r-it->l+1});
	}
	sort(v.begin(),v.end());
	for(int i=0;i<v.size();i++)
	{
   
		if((k-=(v[i].second))<=0)
			return v[i].first;
	}
	return -1;
}
signed main()
{
   
	ios::sync_with_stdio(0);
	cin>>n>>m>>seed>>vmax;
	for(int i=1;i<=n;i++)
	a[i]=(rnd()%vmax)+1,s.insert((node){
   i,i,a[i]});
	while(m--){
   
		int op,l,r;
		int x,y;
		op=(rnd()%4)+1;
		l=(rnd()%n)+1;
		r=(rnd()%n)+1;
		if(l>r)
		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);
    	else if(op==2)
    		assign(l,r,x);
    	else if(op==3)
    		cout<<kth(l,r,x)<<endl;
    	else if(op==4)
    		cout<<qr(l,r,x,y)<<endl;
	}
	return 0;
}