剪贴板 tg3hb1to

【模板】珂朵莉树(ODT) ```cpp #include<bits/stdc++.h> #define int long long #define IT set<ccfily>::iterator using namespace std; int vmax,seed,n,m,a[200005]; int rnd(){ int ret=seed; seed=(seed*7+13)%1000000007; return ret; } struct ccfily{ int l,r; mutable int dat; ccfily(int L,int R=-1,int DAT=0):l(L),r(R),dat(DAT){} bool operator<(const ccfily &a)const{ return l<a.l; } }; set<ccfily> s; int qpow(int x,int y,int mod){ int ans=1%mod; while(y){ if(y&1){ ans=ans*x%mod; } x=x*x%mod; y>>=1; } return ans; } IT split(int p){ IT it=s.lower_bound(ccfily(p)); if(it!=s.end()&&it->l==p){ return it; } it--; int lb=it->l,rb=it->r,date=it->dat; s.erase(it); s.insert(ccfily(lb,p-1,date)); return s.insert(ccfily(p,rb,date)).first; } void assign(int l1,int r1,int val=0){ IT itr=split(r1+1),itl=split(l1); s.erase(itl,itr); s.insert(ccfily(l1,r1,val)); } void add(int l,int r,int val=0){ IT itr=split(r+1),itl=split(l); for(;itl!=itr;itl++){ itl->dat+=val; } return; } int little(int l,int r,int k){ vector< pair<int,int> > vp;vp.clear(); IT itr=split(r+1),itl=split(l); for(;itl!=itr;itl++){ vp.push_back(make_pair(itl->dat,itl->r-itl->l+1)); } sort(vp.begin(),vp.end()); for(vector<pair <int,int> >::iterator itv=vp.begin();itv!=vp.end();itv++){ k-=itv->second; if(k<=0){ return itv->first; } } return -1; } int sum(int l,int r,int cf,int mod){ IT itr=split(r+1),itl=split(l); int ans=0; for(;itl!=itr;itl++){ ans=(ans+(itl->r-itl->l+1)*qpow(itl->dat%mod,cf,mod))%mod; } return ans; } signed main(){ cin>>n>>m>>seed>>vmax; for(int i=1;i<=n;i++){ a[i]=(rnd()%vmax)+1; s.insert(ccfily(i,i,a[i])); } for(int i=1;i<=m;i++){ int op=(rnd()%4)+1; int l=(rnd()%n)+1; int r=(rnd()%n)+1; if(l>r)swap(l,r); int x,y; if(op==3)x=(rnd()%(r-l+1))+1; else x=(rnd()%vmax)+1; if (op==4)y=(rnd()%vmax)+1; if(op==1){ add(l,r,x); } if(op==2){ assign(l,r,x); } if(op==3){ printf("%lld\n",little(l,r,x)); } if(op==4){ printf("%lld\n",sum(l,r,x,y)); } } return 0; }