CF896C Willem, Chtholly and Seniorious

洛咕

题面:请你写一种奇怪的数据结构，支持：

- (1) (l) (r) (x) ：将([l,r]) 区间所有数加上(x)

- (2) (l) (r) (x) ：将([l,r]) 区间所有数改成(x)

- (3) (l) (r) (x) ：输出将([l,r]) 区间从小到大排序后的第(x) 个数是的多少(即区间第(x) 小，数字大小相同算多次，保证 (1leq) (x) (leq) (r-l+1) )

- (4) (l) (r) (x) (y) ：输出([l,r]) 区间每个数字的(x) 次方的和模(y) 的值(即((sum^r_{i=l}a_i^x) ) (mod y) )

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define IT set<node>::iterator
using namespace std;
inline ll read(){
    ll x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
ll n,m,seed,vmax,a[100005];
struct node{
	int l,r;mutable ll val;
	node(int L,int R=-1,ll V=0){l=L,r=R,val=V;}
	bool operator <(const node &x)const{
		return l<x.l;
	}
};
set<node>s;
inline ll rnd(){
    ll res=seed;
    seed=(seed*7+13)%1000000007;
    return res;
}
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 val=it->val;
	s.erase(it);
	s.insert(node(l,pos-1,val));
	return s.insert(node(pos,r,val)).first;
}
inline void add(int l,int r,ll val){
	IT itr=split(r+1),itl=split(l);
	for(;itl!=itr;++itl)itl->val+=val;
	return;
}
inline void assign(int l,int r,ll val){
	IT itr=split(r+1),itl=split(l);
	s.erase(itl,itr);
	s.insert(node(l,r,val));
}
inline ll kth(int l,int r,int k){
    vector<pair<ll,int> >q;
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
		q.push_back(pair<ll,int>(itl->val,itl->r-itl->l+1));
    sort(q.begin(),q.end());
    for(vector<pair<ll,int> >::iterator it=q.begin();it!=q.end();++it){
        k-=it->second;
        if(k<=0)return it->first;
    }
}
inline ll ksm(ll a,ll b,ll c){
	ll cnt=1;a%=c;
	while(b){
		if(b&1)cnt=(1ll*cnt*a)%c;
		a=(1ll*a*a)%c;
		b>>=1;
	}
	return cnt;
}
inline ll ask_sum(int l,int r,ll x,ll y){
    ll ans=0;
    IT itr=split(r+1),itl=split(l);
    for(;itl!=itr;++itl)
		ans+=(ksm(itl->val,x,y)*((itl->r-itl->l+1)%y))%y,ans%=y;
    return ans;
}
int main(){
	n=read();m=read();seed=read();vmax=read();
    for(int i=1;i<=n;++i){
        a[i]=(rnd()%vmax)+1;
        s.insert(node(i,i,a[i]));
    }
    for(int i=1;i<=m;++i){
        int opt=(rnd()%4)+1;
        int l=(rnd()%n)+1,r=(rnd()%n)+1;
        ll x,y;
    	if(l>r)swap(l,r);
    	if(opt==3)x=(rnd()%(r-l+1))+1;
    	else x=(rnd()%vmax)+1;
    	if(opt==4)y=(rnd()%vmax)+1;
    	if(opt==1)add(l,r,x);
    	else if(opt==2)assign(l,r,x);
    	else if(opt==3)printf("%lld
",kth(l,r,x));
    	else if(opt==4)printf("%lld
",ask_sum(l,r,x,y));
    }
    return 0;
}