wrong answer 3rd numbers differ - expected: '732131239', found: '1100243759015'
用cf的数据在本地跑就对,交上就不对,球球啦
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<windows.h>
#define ll long long
using namespace std;
struct node{
ll l,r;
mutable ll v;
node(ll a=-1,ll b=-1,ll c=0){
l=a,r=b,v=c;
}
bool operator <(const node &a) const{
return l<a.l;
}
};
set<node> st;
inline set<node>::iterator split(ll pos){
set<node>::iterator iter=st.lower_bound(node(pos));
if(iter!=st.end()&&iter->l==pos) return iter;
--iter;node temp=*iter;st.erase(iter);
st.insert(node(temp.l,pos-1,temp.v));
return st.insert(node(pos,temp.r,temp.v)).first;
}
inline void assign(ll l,ll r,ll val){
set<node>::iterator itl=split(l),itr=split(r+1);
st.erase(itl,itr);
st.insert((node){l,r,val});
}
inline void add(ll l,ll r,ll ad){
set<node>::iterator itl=split(l),itr=split(r+1);
for(set<node>::iterator iter=itl;iter!=itr;++iter){
iter->v+=ad;
}
}
inline int querykth(ll l,ll r,ll k){
set<node>::iterator itl=split(l),itr=split(r+1);
vector <pair<ll,ll> > v(0);
for(set<node>::iterator iter=itl;iter!=itr;++iter){
v.push_back(make_pair(iter->v,iter->r-iter->l+1));
}
sort(v.begin(),v.end());
for(vector<pair<ll,ll> >::iterator iter=v.begin() ;iter!=v.end();++iter){
k-=iter->second;
if(k<=0) return iter->first;
}
}
inline ll quick(ll a,ll b,ll mod){
a%=mod;
ll c=1;
while(b){
if(b&1) c=(c*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return c;
}
inline ll querypow(ll l,ll r,ll x,ll y){
set<node>::iterator itl=split(l),itr=split(r+1);
ll ans=0;
for(set<node>::iterator iter=itl;iter!=itr;++iter){
ll temp=quick(iter->v,x,y);
ans=(ans+(temp*(iter->r-iter->l+1))%y)%y;
}
return ans;
}
ll n,m,seed,vmax;
inline ll rnd(){
ll ret=seed;
seed=(seed*7+13)%1000000007;
return ret;
}
int main(){
//freopen("1.out","w",stdout);
cin>>n>>m>>seed>>vmax;
for(ll i=1;i<=n;i++){
ll x=(rnd()%vmax)+1;
st.insert((node){i,i,x});
}
ll x,y;
for(ll i=1;i<=m;i++){
ll 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){
printf("%lld\n",querykth(l,r,x));
//Sleep(100);
}else{
printf("%lld\n",querypow(l,r,x,y));
//Sleep(100);
}
//Sleep(100);
}
return 0;
} ```