cf896C Willem, Chtholly and Seniorious

给定一个随机序列,每次给定4个随机操作

  1. 区间加一个数
  2. 区间置为一个数
  3. 求区间第$k$大值
  4. 求区间$[l,r]$里$\sum_{i=l}^{i=r} {a_i}^x$

由于是随机数列,所以可以将一个序列划分为一段一段的值域,对值域进行操作即可,也就是暴力,lxl把它称为$old~driver~tree$

复杂度:数据结构有一个$logn$,$oldd~river~tree$在随机数据下的均摊是$O(n)$的,总共是$O(nlogn)$,因为每次$add$操作不会改变区间值域的个数,$set$会推平很多区间,一个小区间最多被推平一次,每次询问最多多产生$2$个区间(相对于推平操作而言是很小的),在4个操作中,$\frac{1}{4}$的概率推平$O(n)$个区间,$\frac{2}{4}$的概率增加1~2个区间(询问),$\frac{1}{4}$的概率什么也不做。相当于每个区间访问$4$次就能删除(与其他合并)了,所以复杂度是$O(n)$的,再带上$set$的$log$,总共是$nlogn$

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int readInt()
{
char c;int tmp=0,x=1;c=getchar();
while(c>'9' || c<'0') {if(c=='-') x=-1;c=getchar();}
while(c>='0' && c<='9') {tmp=tmp*10+c-'0';c=getchar();}
return tmp*x;
}
const int maxn=(int)1e5+5;
int n,m,seed,vmax,a[maxn],ret;
int rnd()
{
ret=seed;
seed=((ll)seed*7+13)%1000000007;
return ret;
}
typedef pair<int ,int > pii;
#define MP make_pair
#define fir first
#define sec second
struct node{
int l,r;
mutable ll val;
bool operator<(const node&oth)const{
return l <oth.l;
}
node(int l=0,int r=0,ll val=0): l(l),r(r),val(val) {}
};
set<node > intev;
typedef set<node >::iterator seto;
void split(int pos)
{
seto ite=intev.lower_bound(node(pos,-1,-1));
if(ite==intev.end() || ite->l>pos) {
--ite;
int L=ite->l,R=ite->r;
ll val=ite->val;
intev.erase(ite);
intev.insert(node(L,pos-1,val));
intev.insert(node(pos,R,val));
}
}
ll quickpow(ll x,int k,ll mo)
{
ll ret=1;
while(k>0) {
if(k&1) ret=(ret*x)%mo;
x=x*x%mo;
k>>=1;
}
return ret;
}
vector<pair<ll,int > > par;
int main()
{
n=readInt(),m=readInt(),seed=readInt(),vmax=readInt();
for(int i=1;i<=n;i++) a[i]=rnd()%vmax +1;
for(int i=1;i<=n;) {
int R=i+1;
while(a[R]==a[i]) R++;
intev.insert(node(i,R-1,a[i]*1ll));
i=R;
}
int op,l,r,x,y;
for(int i=1;i<=m;i++) {
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;
split(l);
if(r<=n-1) split(r+1);
seto iteL=intev.lower_bound(node(l,-1,-1));
seto iteR=intev.upper_bound(node(r,-1,-1));
if(op==1) {
for(seto ite=iteL;ite!=iteR;++ite) ite->val+=x;
}else if(op==2) {
intev.erase(iteL,iteR);
intev.insert(node(l,r,x));
}else if(op==3) {
par.clear();
for(seto ite=iteL;ite!=iteR;++ite)
par.push_back(MP(ite->val,ite->r-ite->l+1));
sort(par.begin(),par.end());
for(int i=0;i<(int)par.size();i++) {
x-=par[i].sec;
if(x<=0) {printf("%lld\n",par[i].fir);break;}
}
assert(x<=0);
}else if(op==4) {
ll ans=0;
for(seto ite=iteL;ite!=iteR;++ite){
ll valu=quickpow(ite->val%(1ll*y),x,y)%y;
valu=valu*(ite->r-ite->l+1)%y;
ans=(ans+valu)%y;
}
printf("%lld\n",ans);
}
}
return 0;
}