cf896C Willem, Chtholly and Seniorious

Posted on |

给定一个随机序列，每次给定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;
}