因为询问是关于一段连续区间内的操作的,所以对操作构建线段树,这里每个点维护若干个不交的区间,每个区间((l,r,a,b))表示区间([l,r])内的数要变成(ax+b)
每次把新操作加入线段树中下一个叶子,然后如果某个节点里所有操作都加进去了,就条到父亲,把两个儿子的信息合并到父亲上.这里合并就是把两个区间集合合并成一个,例如两个区间([a,c])和([b,d](ale ble cle d))会合并成([a,b),[b,c),[c,d]).合并出来的区间如果属于两个集合中元素的交,那么对应的(ax+b)就是(a_r(a_l+b_l)+b_r=a_ra_lx+a_rb_l+b_r).
查询时依次找到对应的线段树节点,然后在区间集合上二分出(k)元素所在的区间,把(ans)更新成(a*ans+b)即可
#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
#define db double
using namespace std;
const int N=6e5+10;
LL rd()
{
LL x=0,w=1;char ch=0;
while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*w;
}
int n,mod,m,q,tt,ans;
struct node
{
int l,r,a,b;
node(){}
node(int nl,int nr,int na,int nb){l=nl,r=nr,a=na,b=nb;}
node operator + (const node &bb) const {return node(max(l,bb.l),min(r,bb.r),1ll*a*bb.a%mod,(1ll*b*bb.a+bb.b)%mod);}
}a[N*40];
#define mid ((l+r)>>1)
int va[N],aq[N<<2][2];
void modif(int o,int l,int r,node x)
{
if(l==r){a[++tt]=x,aq[o][0]=aq[o][1]=tt;return;}
if(m<=mid) modif(o<<1,l,mid,x);
else modif(o<<1|1,mid+1,r,x);
if(m<r) return;
int l1=aq[o<<1][0],r1=aq[o<<1][1],l2=aq[o<<1|1][0],r2=aq[o<<1|1][1];
aq[o][0]=tt+1;
while(l1<=r1||l2<=r2)
{
if(l2>r2||(l1<=r1&&a[l1].r<a[l2].l)) a[++tt]=a[l1];
else if(l1>r1||(l2<=r2&&a[l2].r<a[l1].l)) a[++tt]=a[l2];
else
{
if(a[l1].l<a[l2].l) a[++tt]=node(a[l1].l,a[l2].l-1,a[l1].a,a[l1].b);
else if(a[l1].l>a[l2].l) a[++tt]=node(a[l2].l,a[l1].l-1,a[l2].a,a[l2].b);
if(tt>aq[o][0]) a[tt].l=max(a[tt].l,a[tt-1].r+1);
if(a[tt].l>a[tt].r) --tt;
a[++tt]=a[l1]+a[l2];
}
if(tt!=aq[o][0]) a[tt].l=max(a[tt].l,a[tt-1].r+1);
if(a[tt].l>a[tt].r) --tt;
if(l1<=r1&&l2<=r2&&a[l1].r==a[l2].r) ++l1,++l2;
else if(l2>r2||(l1<=r1&&a[l1].r<a[l2].r)) ++l1;
else ++l2;
}
aq[o][1]=tt;
}
void wk(int o,int x)
{
int ll=aq[o][0],rr=aq[o][1],z=0;
while(ll<=rr)
{
int md=(ll+rr)>>1;
if(a[md].l<=x) z=md,ll=md+1;
else rr=md-1;
}
if(a[z].r>=x) ans=(1ll*ans*a[z].a+a[z].b)%mod;
}
void quer(int o,int l,int r,int ll,int rr,int x)
{
if(ll<=l&&r<=rr){wk(o,x);return;}
if(ll<=mid) quer(o<<1,l,mid,ll,rr,x);
if(rr>mid) quer(o<<1|1,mid+1,r,ll,rr,x);
}
int main()
{
int ty=rd()&1;
n=rd(),mod=rd();
for(int i=1;i<=n;++i) va[i]=rd();
q=rd();
for(int i=1;i<=q;++i)
{
int op=rd(),l=rd()^(ans*ty),r=rd()^(ans*ty);
if(op==1)
{
int aa=rd(),bb=rd();
++m;
modif(1,1,q,node(l,r,aa,bb));
}
else
{
int x=rd()^(ans*ty);
ans=va[x];
quer(1,1,q,l,r,x);
printf("%d
",ans);
}
}
return 0;
}