中文题面
珂朵莉树的板子……这篇文章很不错
据说还有奈芙莲树和瑟尼欧里斯树……
等联赛考完去学一下（逃
1 //minamoto 2 #include<bits/stdc++.h> 3 #define IT set<node>::iterator 4 #define ll long long 5 using namespace std; 6 const int mod7=1e9+7,mod9=1e9+9,N=1e5+5; 7 ll ksm(ll a,ll b,ll mod){ 8 ll res=1;a%=mod; 9 while(b){ 10 if(b&1) res=res*a%mod; 11 a=a*a%mod,b>>=1; 12 } 13 return res; 14 } 15 struct node{ 16 int l,r;mutable ll v; 17 node(int L,int R=-1,ll V=0):l(L),r(R),v(V){} 18 inline bool operator<(const node &b)const 19 {return l<b.l;} 20 }; 21 set<node> s; 22 IT split(int pos){ 23 IT it=s.lower_bound(node(pos)); 24 if(it!=s.end()&&it->l==pos) return it; 25 --it; 26 int l=it->l,r=it->r;ll v=it->v; 27 s.erase(it),s.insert(node(l,pos-1,v)); 28 return s.insert(node(pos,r,v)).first; 29 } 30 void add(int l,int r,ll val=1){ 31 IT itr=split(r+1),itl=split(l); 32 for(;itl!=itr;++itl) itl->v+=val; 33 } 34 void assign(int l,int r,ll val=0){ 35 IT itr=split(r+1),itl=split(l); 36 s.erase(itl,itr),s.insert(node(l,r,val)); 37 } 38 ll rk(int l,int r,int k){ 39 vector<pair<ll,int> > mp; 40 IT itr=split(r+1),itl=split(l); 41 mp.clear(); 42 for(;itl!=itr;++itl) 43 mp.push_back(pair<ll,int>(itl->v,itl->r-itl->l+1)); 44 sort(mp.begin(),mp.end()); 45 for(vector<pair<ll,int> >::iterator it=mp.begin();it!=mp.end();++it){ 46 k-=it->second; 47 if(k<=0) return it->first; 48 } 49 return -1ll; 50 } 51 ll sum(int l,int r,int ex,int mod){ 52 IT itr=split(r+1),itl=split(l);ll res=0; 53 for(;itl!=itr;++itl) 54 res=(res+1ll*(itl->r-itl->l+1)*ksm(itl->v,ex,mod))%mod; 55 return res; 56 } 57 int n,m;ll seed,vmax; 58 ll rnd(){ 59 ll res=seed;seed=(seed*7+13)%mod7; 60 return res; 61 } 62 ll a[N]; 63 int main(){ 64 // freopen("testdata.in","r",stdin); 65 scanf("%d %d %lld %lld",&n,&m,&seed,&vmax); 66 for(int i=1;i<=n;++i){ 67 a[i]=(rnd()%vmax)+1,s.insert(node(i,i,a[i])); 68 } 69 s.insert(node(n+1,n+1,0)); 70 int lines=0; 71 for(int i=1;i<=m;++i){ 72 int op=int(rnd()%4)+1; 73 int l=int(rnd()%n)+1; 74 int r=int(rnd()%n)+1; 75 if(l>r) swap(l,r);int x,y; 76 if(op==3) x=int(rnd()%(r-l+1))+1; 77 else x=int(rnd()%vmax)+1; 78 if(op==4) y=int(rnd()%vmax)+1; 79 switch(op){ 80 case 1:add(l,r,x);break; 81 case 2:assign(l,r,x);break; 82 case 3:printf("%lld\n",rk(l,r,x));break; 83 case 4:printf("%lld\n",sum(l,r,x,y));break; 84 } 85 } 86 return 0; 87 }
