调了一天了真的吐了
#include<algorithm>
#include<bitset>
#include<cctype>
#include<cerrno>
#include<clocale>
#include<cmath>
#include<complex>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<utility>
#include<vector>
#include<cwchar>
#include<cwctype>
#include<chrono>
#include<random>
#include<unordered_map>
using namespace std;
//#define int long long
#define ll long long
#define ull unsigned long long
#define rll register long long
#define ri register int
#define il inline
#define str set<ct>::iterator
const int INF=0x7fffffff,MOD=1e9+7;
int n,m;
ll seed,vmax;
struct ct{
int l,r;
mutable ll v;
ct(int L,int R=-1,ll V=0){
l=L,r=R,v=V;
}
bool operator <(const ct &a)const{
return l<a.l;
}
};
set<ct> s;
il ll read(){
ll x=0,y=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')
y=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*y;
}
il str split(int pos){
str it=s.lower_bound(ct(pos));
if(it!=s.end()&&it->l==pos)
return it;
it--;
int l=it->l,r=it->r;
ll v=it->v;
s.erase(it);
return s.insert(ct(pos,r,v)).first;
}
il void assign(int l,int r,ll v) {
str it2=split(r+1),it1=split(l);
s.erase(it1,it2);
s.insert(ct(l,r,v));
}
il void add(int l,int r,ll val){
str it2=split(r+1),it1=split(l);
for(;it1!=it2;it1++)
it1->v+=val;
}
il ll rk(int l,int r,int k){
vector<pair<ll,int>> p;
str it2=split(r+1),it1=split(l);
p.clear();
for(;it1!=it2;it1++)
p.push_back(pair<ll,int>(it1->v,it1->r-it1->l+1));
sort(p.begin(),p.end());
for(vector<pair<ll,int>>::iterator it=p.begin();it!=p.end();it++){
k-=it->second;
if(k<=0)
return it->first;
}
return -1;
}
il ll qpow(ll x,ll y,ll p){
ll res=1,ans=x%p;
while(y){
if(y&1)
res=res*ans%p;
ans=ans*ans%p;
y>>=1;
}
return res;
}
il ll sum(int l,int r,int x,int y){
str it2=split(r+1),it1=split(l);
ll res=0;
for(;it1!=it2;it1++)
res=(res+1ll*(it1->r-it1->l+1)*qpow(it1->v,1ll*x,1ll*y))%y;
return res;
}
il ll rnd(){
ll ret=seed;
seed=(seed*7+13)%MOD;
return ret;
}
signed main(){
n=read(),m=read(),seed=read(),vmax=read();
for(ri i=1;i<=n;i++)
s.insert(ct(i,i,rnd()%vmax+1));
s.insert(ct(n+1,n+1,0));
for(ri i=1;i<=m;i++){
int op=int(rnd()%4)+1,l=int(rnd()%n)+1,r=int(rnd()%n)+1,x,y;
if(l>r)
swap(l,r);
if(op==3){
x=int(rnd()%(r-l+1))+1;
printf("%lld\n",rk(l,r,x));
}
else
x=int(rnd()%vmax) +1;
if(op==1)
add(l,r,1ll*x);
if(op==2)
assign(l,r,1ll*x);
if(op==4){
y=int(rnd()%vmax)+1;
printf("%lld\n",sum(l,r,x,y));
}
}
return 0;
}
感激不尽/kk