https://codeforces.com/gym/105139/problem/F24湖北省赛F
看了一下前面两种操作,做法不是很明显
后面两种操作,一看就是可持久化线段树,单点修改,版本复制
接下来解决前面的两种操作
第一个操作
两个相同的合成一个新的(3+3->4),感觉是二进制,
举个例子,[1,2,2,4]->[1,3,4]最大是4, 我们模拟二进制运算,我们维护()就可以转化成二进制,(1021)->(1101),找最高位1的位置即可,__lg函数得到答案
第二个操作
沿着第一个操作思路以及例子,k=3,(1101)+(100)->(10001),发现高位的1,1都向前进了,比k低位的1不会有贡献,我们就可以模拟这个操作,计算贡献
#include<iostream>
#define INF (1ll<<61)
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int mo=19260817;
const int N=1e6+9;
int a[N];
int n,m;
ll A;
int p,q;
//可持久化线段树
struct KCJSEG{struct node{int l,r;ll val;}seg[N<<5];#define tl(id) seg[id].l#define tr(id) seg[id].r#define pushup(id) seg[id].val=seg[tl(id)].val+seg[tr(id)].valint root[N],index,mx;int inrange(int L,int R,int l,int r){return L>=l && R<=r;}int outofrange(int L,int R,int l,int r){return L>r || l>R;}void build(int &id,int l,int r){id=++index;if(l==r){seg[id].val=a[l];return;}int mid=(l+r)>>1;build(tl(id),l,mid);build(tr(id),mid+1,r);pushup(id);}void update(int post,int &curr,int l,int r,int pos,int v){curr=++index;seg[curr]=seg[post];if(l==r){seg[curr].val=v;return;}int mid=(l+r)>>1;if(mid>=pos){update(tl(post),tl(curr),l,mid,pos,v);}else{update(tr(post),tr(curr),mid+1,r,pos,v);}pushup(curr);}ll query(int curr,int L,int R,int l,int r){if(inrange(L,R,l,r)){return seg[curr].val;}else if(!outofrange(L,R,l,r)){int mid=(L+R)>>1;return query(tl(curr),L,mid,l,r)+query(tr(curr),mid+1,R,l,r);}else{return 0;}}
}tr;
void rnd(){ A*=7;A+=13;A%=mo;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>A>>p>>q;for(int i=1;i<=n;i++){rnd();a[i]=(A%q)+1;}for(int i=1;i<=n;i++){a[i]=1ll<<a[i];}tr.build(tr.root[0],1,n);for(int i=1;i<=m;i++){tr.root[i]=tr.root[i-1];rnd();int opt=(A%p)+1;if(opt==1){rnd();int L=(A%n)+1;rnd();int R=(A%n)+1;int l=min(L,R);int r=max(L,R);ll ans=tr.query(tr.root[i],1,n,l,r);cout<<__lg(ans)<<'\n';//log2()}else if(opt==2){rnd();int L=(A%n)+1;rnd();int R=(A%n)+1;int l=min(L,R);int r=max(L,R);rnd();int k=(A%q)+1;ll res=tr.query(tr.root[i],1,n,l,r);ll ans=0;for(int j=0;res;j++){if(j>=k){if(res&1){ans+=(1ll<<(j+1))%mod;ans%=mod;}else{break;}}res>>=1;}cout<<(ans%mod+mod)%mod<<'\n';}else if(opt==3){rnd();int pos=(A%n)+1;rnd();ll k=(A%q)+1;k=(1ll<<k);tr.update(tr.root[i-1],tr.root[i],1,n,pos,k);}else{rnd();int t=A%i;tr.root[i]=tr.root[t];}}return 0;
}