2019.01.19 codeforces 896C.Willem, Chtholly and Seniorious(ODT)
程序员文章站
2024-02-24 11:19:46
...
传送门
出处(万恶之源)
题目简述:
- 区间赋值
- 区间加
- 区间所有数k次方和
- 区间第k小
思路:直接上。
不会的点这里
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
const int N=1e5+5;
typedef long long ll;
typedef pair<ll,int> pli;
vector<pli>q;
struct Node{
int l,r;
mutable ll v;
Node(int l_,int r_=-1,ll v_=0):l(l_),r(r_),v(v_){}
friend inline bool operator<(const Node&a,const Node&b){return a.l<b.l;}
};
set<Node>S;
typedef set<Node>::iterator It;
inline It split(int pos){
It it=S.lower_bound(Node(pos));
if(it!=S.end()&&it->l==pos)return it;
--it;
int l=it->l,r=it->r;
ll v=it->v;
return S.erase(it),S.insert(Node(l,pos-1,v)),S.insert(Node(pos,r,v)).first;
}
inline int ksm(ll a,int p,ll mod){int ret=1;a%=mod;for(;p;p>>=1,a=a*a%mod)if(p&1)ret=a*ret%mod;return ret;}
inline void assign(int l,int r,ll v){
It R=split(r+1),L=split(l);
return S.erase(L,R),(void)S.insert(Node(l,r,v));
}
inline void add(int l,int r,ll v){
It L=split(l),R=split(r+1);
for(It it=L;it!=R;++it)(it->v)+=v;
}
inline ll Rank(int l,int r,int kth){
It R=split(r+1),L=split(l);
q.clear();
for(It it=L;it!=R;++it)q.push_back(pli(it->v,it->r-it->l+1));
sort(q.begin(),q.end());
for(ri i=0;i<q.size();++i){
kth-=q[i].second;
if(kth<=0)return q[i].first;
}
return -1;
}
inline ll query(int l,int r,int k,ll mod){
ll ret=0;
It L=split(l),R=split(r+1);
for(It it=L;it!=R;++it)ret=(ret+(ll)(it->r-it->l+1)*ksm(it->v,k,mod)%mod)%mod;
return ret;
}
int n,m,vmax,seed;
inline int rd(){
int ret=seed;
seed=(7ll*seed+13)%1000000007;
return ret;
}
int main(){
n=read(),m=read(),seed=read(),vmax=read();
for(ri i=1;i<=n;++i)S.insert(Node(i,i,rd()%vmax+1));
for(ri i=1,op,L,R,x,y;i<=m;++i){
op=rd()%4+1,L=rd()%n+1,R=rd()%n+1;
if(L>R)swap(L,R);
if(op==3)x=rd()%(R-L+1)+1;
else x=rd()%vmax+1;
if(op==4)y=rd()%vmax+1;
switch(op){
case 1:add(L,R,x);break;
case 2:assign(L,R,x);break;
case 3:cout<<Rank(L,R,x)<<'\n';break;
default:cout<<query(L,R,x,y)<<'\n';
}
}
return 0;
}
推荐阅读
-
2019.01.19 codeforces 896C.Willem, Chtholly and Seniorious(ODT)
-
Codeforces896C Willem, Chtholly and Seniorious
-
[ODT] Codeforces 896C. Willem, Chtholly and Seniorious
-
【题解】Willem, Chtholly and Seniorious Codeforces 896C ODT
-
Codeforces - Willem, Chtholly and Seniorious
-
CodeForces - 896C Willem, Chtholly and Seniorious【ODT珂朵莉树】
-
Codeforces:896C-Willem, Chtholly and Seniorious(odt模板)
-
CodeForces - 897E Willem, Chtholly and Seniorious(珂朵莉树)
-
Codeforces896 C. Willem, Chtholly and Seniorious(ODT)
-
cf896C. Willem, Chtholly and Seniorious(ODT)