CF896C Willem, Chtholly and Seniorious（珂朵莉树）

中文题面

珂朵莉树的板子……这篇文章很不错

据说还有奈芙莲树和瑟尼欧里斯树……

等联赛考完去学一下（逃

 //minamoto

 #include<bits/stdc++.h>

 #define IT set<node>::iterator

 #define ll long long

 using namespace std;

 const int mod7=1e9+,mod9=1e9+,N=1e5+;

 ll ksm(ll a,ll b,ll mod){

     ll res=;a%=mod;

     while(b){

         if(b&) res=res*a%mod;

         a=a*a%mod,b>>=;

     }

     return res;

 }

 struct node{

     int l,r;mutable ll v;

     node(int L,int R=-,ll V=):l(L),r(R),v(V){}

     inline bool operator<(const node &b)const

     {return l<b.l;}

 };

 set<node> s;

 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;

     s.erase(it),s.insert(node(l,pos-,v));

     return s.insert(node(pos,r,v)).first;

 }

 void add(int l,int r,ll val=){

     IT itr=split(r+),itl=split(l);

     for(;itl!=itr;++itl) itl->v+=val;

 }

 void assign(int l,int r,ll val=){

     IT itr=split(r+),itl=split(l);

     s.erase(itl,itr),s.insert(node(l,r,val));

 }

 ll rk(int l,int r,int k){

     vector<pair<ll,int> > mp;

     IT itr=split(r+),itl=split(l);

     mp.clear();

     for(;itl!=itr;++itl)

     mp.push_back(pair<ll,int>(itl->v,itl->r-itl->l+));

     sort(mp.begin(),mp.end());

     for(vector<pair<ll,int> >::iterator it=mp.begin();it!=mp.end();++it){

         k-=it->second;

         if(k<=) return it->first;

     }

     return -1ll;

 }

 ll sum(int l,int r,int ex,int mod){

     IT itr=split(r+),itl=split(l);ll res=;

     for(;itl!=itr;++itl)

     res=(res+1ll*(itl->r-itl->l+)*ksm(itl->v,ex,mod))%mod;

     return res;

 }

 int n,m;ll seed,vmax;

 ll rnd(){

     ll res=seed;seed=(seed*+)%mod7;

     return res;

 }

 ll a[N];

 int main(){

 //    freopen("testdata.in","r",stdin);

     scanf("%d %d %lld %lld",&n,&m,&seed,&vmax);

     for(int i=;i<=n;++i){

         a[i]=(rnd()%vmax)+,s.insert(node(i,i,a[i]));

     }

     s.insert(node(n+,n+,));

     int lines=;

     for(int i=;i<=m;++i){

         int op=int(rnd()%)+;

         int l=int(rnd()%n)+;

         int r=int(rnd()%n)+;

         if(l>r) swap(l,r);int x,y;

         if(op==) x=int(rnd()%(r-l+))+;

         else x=int(rnd()%vmax)+;

         if(op==) y=int(rnd()%vmax)+;

         switch(op){

             case :add(l,r,x);break;

             case :assign(l,r,x);break;

             case :printf("%lld\n",rk(l,r,x));break;

             case :printf("%lld\n",sum(l,r,x,y));break;

         }

     }

     return ;

 }