1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;++i)
using namespace std;
const int md = 1e9+7;
const int N = 1e5+10;
int n,m,seed,v_max;
int a[N];
int rnd(){
int ret = seed;
seed = (seed*7+13)%md;
return ret;
}
struct Node{
int l,r;
mutable int val;
Node(int ll,int rr = -1,int vall= 0):l(ll),r(rr),val(vall){};
inline bool operator < (const Node &b)const{
return l<b.l;
}
};
set<Node> s;//原始的珂朵莉树
inline int Qpow(int a,int b,int mod){
int ret = 1;
a%=mod;
while(b){
if(b&1)(ret*=a)%=mod;
b>>=1;
(a*=a)%=mod;
}
return ret;
}
inline auto split(int pos){
auto 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->val;
s.erase(it);
s.insert(Node(L,pos-1,v));
return s.insert(Node(pos,R,v)).first;
}
inline auto assign(int l,int r,int v){//把(l,r)改为v
auto itL = split(l),itR = split(r+1);
s.erase(itL,itR);
s.insert(Node(l,r,v));
}
inline void add(int l,int r,int v){//把(l,r)加上v
auto itL = split(l),itR = split(r+1);
for(;itL!=itR;itL++)itL->val+=v;
}
inline int rnk(int l,int r,int k){
vector<pair<int,int>> vec;
auto itL = split(l),itR = split(r+1);
for(;itL!=itR;itL++)vec.push_back(make_pair(itL->val,itL->r-itL->l+1));
sort(vec.begin(),vec.end());
for(auto it = vec.begin();it!=vec.end();it++){
k-=it->second;
if(k<=0)return it->first;
}
return -1;
}
inline int sum(int l,int r,int ex,int mod){
auto itL = split(l),itR = split(r+1);
int res = 0;
for(;itL!=itR;itL++){
(res+=Qpow(itL->val,ex,mod)*(itL->r-itL->l+1))%=mod;
}
return res;
}
signed main(){
cin>>n>>m>>seed>>v_max;
FOR(i,1,n)s.insert(Node(i,i,rnd()%v_max+1));
FOR(i,1,m){
int op = (rnd()%4)+1,l = (rnd()%n)+1,r = (rnd()%n)+1,x,y;
// cout<<"Op "<<op<<"\n "<<l<<" "<<r<<endl;
if(l>r)swap(l,r);
if(op==3)x = rnd()%(r-l+1)+1;
else x = rnd()%v_max+1;
if(op==4)y = rnd()%v_max+1;
if(op==1)add(l,r,x);
if(op==2)assign(l,r,x);
if(op==3)cout<<rnk(l,r,x)<<endl;
if(op==4)cout<<sum(l,r,x,y)<<endl;
// bl();
}
}
|
