description
给出\(n\)个变换，第\(i\)个变换是将区间中\(l_i,r_i\)的数\(x\)变成\((a_ix+b_i)\mod m\)。
每次会新增一个变换，或者查询询问如果进行编号\([s,t]\)的操作，第\(k\)个数会变成多少。
\(n\le10^5,q\le6\times10^5\)
sol
二进制分组。
按顺序把变化插入线段树，如果线段树的某个满了就向上归并两个儿子的变换。
\(a_j(a_ix+b_i)+b_j=a_ia_jx+a_jb_i+b_j\)就是两个变换的合并。
查询的时候找到线段树的对应节点（这些节点一定都是合并好了的），然后在维护出的变化序列上二分找到第\(k\)个位置，直接算即可。
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int gi(){
int x=0,w=1;char ch=getchar();
while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if (ch=='-') w=0,ch=getchar();
while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return w?x:-x;
}
const int N = 1e5+5;
struct node{int p,a,b;}t[N*30];
int Type,n,m,q,mod,val[N],L[N<<2],R[N<<2],cnt,ans;
void modify(int x,int l,int r,int ql,int qr,int a,int b){
if (l==r){
L[x]=cnt+1;
if (ql>1) t[++cnt]=(node){ql-1,1,0};
t[++cnt]=(node){qr,a,b};
if (qr<n) t[++cnt]=(node){n,1,0};
R[x]=cnt;return;
}
int mid=l+r>>1;
if (m<=mid) modify(x<<1,l,mid,ql,qr,a,b);
else modify(x<<1|1,mid+1,r,ql,qr,a,b);
if (m<r) return;
int i=L[x<<1],j=R[x<<1],u=L[x<<1|1],v=R[x<<1|1];
L[x]=cnt+1;
while (i<=j&&u<=v){
t[++cnt]=(node){min(t[i].p,t[u].p),1ll*t[i].a*t[u].a%mod,(1ll*t[i].b*t[u].a+t[u].b)%mod};
if (t[i].p==t[u].p) ++i,++u;else if (t[i].p<t[u].p) ++i;else ++u;
}
R[x]=cnt;
}
void calc(int x,int k){
int l=L[x],r=R[x],res=0;
while (l<=r){
int mid=l+r>>1;
if (t[mid].p>=k) res=mid,r=mid-1;
else l=mid+1;
}
ans=(1ll*ans*t[res].a+t[res].b)%mod;
}
void query(int x,int l,int r,int ql,int qr,int k){
if (l>=ql&&r<=qr) {calc(x,k);return;}
int mid=l+r>>1;
if (ql<=mid) query(x<<1,l,mid,ql,qr,k);
if (qr>mid) query(x<<1|1,mid+1,r,ql,qr,k);
}
int main(){
Type=gi()&1;n=gi();mod=gi();
for (int i=1;i<=n;++i) val[i]=gi();
q=gi();while (q--){
int op=gi(),l=gi(),r=gi();
if (Type) l^=ans,r^=ans;
if (op==1){
int a=gi(),b=gi();++m;
modify(1,1,100000,l,r,a,b);
}else{
int k=gi();if (Type) k^=ans;
ans=val[k];
query(1,1,100000,l,r,k);
printf("%d\n",ans);
}
}
return 0;
}