wa on #6。

Willem, Chtholly and Seniorious

code:

#include<bits/stdc++.h>
#define IT set<node>::iterator 
#define int long long
using namespace std;
int fpow(int x,int y,int z)
{
	if(y==0)return 1;
	if(y==1)return x;
	int d=fpow(x,y/2,z)%z;
	if(y%2)return (d*d)%z*x%z;
	return d*d%z;
}
struct node
{
	int l,r;
	mutable int x;
	node(int L,int R=-1,int X=0): l(L),r(R),x(X){}
	bool operator<(const node &o)const 
	{
	    return l < o.l;
	}
};set<node> s;
IT spilit(int pos)
{
	IT it=s.lower_bound(node(pos));
	if(it!=s.end()&&it->l==pos)return it;
	it--;
	int L=it->l,R=it->r,V=it->x;
	s.erase(it);
	s.insert(node(L,pos-1,V));
	return s.insert(node(pos,R,V)).first;
}
void assign_val(int l,int r,int val)
{
	IT itr=spilit(r+1),itl=spilit(l);
	s.erase(itl,itr);
	s.insert(node(l,r,val));
}
void add(int l,int r,int v)
{
	IT itr=spilit(r+1),itl=spilit(l);
	for(;itl!=itr;itl++)itl->x+=v;
}
int kth(int l,int r,int k)
{
    vector<pair<int,int> >a;
    IT itr=spilit(r+1),itl=spilit(l);
    for(IT iter=itl;iter!=itr;iter++)
        a.push_back(pair<int,int>(iter->x,(iter->r)-(iter->l)+1));
    sort(a.begin(),a.end());
    for(vector< pair<int,int> >::iterator iter=a.begin();iter!=a.end();iter++)
    {
        k-=iter->second;
        if(k<=0)return iter->first;
    }
    return -1;
}
int ask(int l,int r,int x,int y)
{
	IT itr=spilit(r+1),itl=spilit(l);
	int ans=0;
	for(;itl!=itr;itl++)(ans+=(fpow(itl->x,x,y)*(itl->r-itl->l+1))%y)%=y;
	return ans;
}
int n,m,seed,vmax;
int r()
{
	int ret=seed;
	seed=(seed*7ll+13)%1000000007ll;
	return ret;
}
signed main()
{
	cin>>n>>m>>seed>>vmax;
	for(int i=1;i<=n;i++)s.insert(node(i,i,r()%vmax+1));
	s.insert(node(n+1,n+1,0));
	while(m--)
	{
		int op=r()%4+1,l=r()%n+1,rr=r()%n+1;
		if(l>rr)swap(l,rr);
		if(op==1)
		{
			int x=r()%vmax+1;
			add(l,rr,x);
		}
		if(op==2)
		{
			int x=r()%vmax+1;
			assign_val(l,rr,x);
		}		
		if(op==3)
		{
			int x=r()%(rr-l+1)+1;
			cout<<kth(l,rr,x)<<endl;
		}	
		if(op==4)
		{
			int x=r()%vmax+1;
			int y=r()%vmax+1;
			cout<<ask(l,rr,x,y)<<endl;
		}
	}
	return 0;
}