【线段树+归并】玄学

归并, 线段树

传送阵：UOJ46

清华集训2014

思路：建一个关于操作的线段树，每个区间维护这些操作下变化 用类似差分的方法存 如果一个区间满了就用归并进行合并（因为插入是从左到右的）

注意：由于只有100000个修改，线段树区间只要开到100000 注意挂链的空间（每层最多100000*3个标记，一共log层）

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
#define N 300000
LL fe,n,m,xb,mo,ans1,ans2,op,x,y,z,p,q,ans,tot,a[N];
struct sege{LL tt,ww;}pos[N*2];
struct node{LL pos,p,q;}f[N*30];
LL getint(){
	char ch; LL sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar())
	 sum=sum*10+ch-'0';
	return sum;
}
void merge(node &x,node y){x.p=(LL)x.p*y.p%mo; x.q=(LL)((LL)x.q*y.p+y.q)%mo;}
void update(LL cur){
	LL tt1=pos[cur<<1].tt,ww1=pos[cur<<1].ww;
	LL tt2=pos[cur<<1|1].tt,ww2=pos[cur<<1|1].ww;
	pos[cur].tt=xb+1;
	f[++xb].pos=1;
	f[xb].p=f[tt1].p*f[tt2].p%mo; f[xb].q=(f[tt1].q*f[tt2].p+f[tt2].q)%mo;
	tt1++; tt2++;
	for (;tt1<=ww1 && tt2<=ww2;){
		if (f[tt1].pos<f[tt2].pos){f[++xb]=f[tt1]; merge(f[xb],f[tt2-1]); tt1++;}
		else if (f[tt1].pos>f[tt2].pos){f[++xb]=f[tt1-1]; f[xb].pos=f[tt2].pos; merge(f[xb],f[tt2]); tt2++;}
		else{f[++xb]=f[tt1]; merge(f[xb],f[tt2]); tt1++; tt2++;}
	}
	for (;tt1<=ww1;){f[++xb]=f[tt1]; merge(f[xb],f[ww2]); tt1++;}
	for (;tt2<=ww2;){f[++xb]=f[ww1]; f[xb].pos=f[tt2].pos; merge(f[xb],f[tt2]); tt2++;}
	pos[cur].ww=xb;
}
void change(LL cur,LL l,LL r,LL k,LL L,LL R,LL p,LL q){
	if (l==r){
		pos[cur].tt=xb+1;
		if (L!=1){f[++xb].pos=1; f[xb].p=1; f[xb].q=0;}
		f[++xb].pos=L; f[xb].p=p; f[xb].q=q;
		if (R!=n){f[++xb].pos=R+1; f[xb].p=1; f[xb].q=0;}
		pos[cur].ww=xb;
		return;
	}
	LL mid=(l+r)>>1;
	if (k<=mid) change(cur<<1,l,mid,k,L,R,p,q);
	if (k>mid) change(cur<<1|1,mid+1,r,k,L,R,p,q);
	if (k==r) update(cur);
}
LL lower(LL tt,LL ww,LL x){
	LL l=tt,r=ww,ss;
	while (l<=r){
		LL mid=(l+r)>>1;
		if (f[mid].pos<=x){ss=mid; l=mid+1;}
		else r=mid-1;
	}
	return ss;
}
void query(LL cur,LL l,LL r,LL L,LL R,LL x){
	if (L<=l && R>=r){
		LL tt=pos[cur].tt,ww=pos[cur].ww;
		LL tmp=lower(tt,ww,x);
		ans1=(LL)ans1*f[tmp].p%mo; ans2=(LL)((LL)ans2*f[tmp].p+f[tmp].q)%mo;
		return;
	}
	LL mid=(l+r)>>1;
	if (L<=mid) query(cur<<1,l,mid,L,R,x);
	if (R>mid) query(cur<<1|1,mid+1,r,L,R,x);
}
int main(){
	fe=getint(); n=getint(); mo=getint();
	for (LL i=1;i<=n;i++) a[i]=getint();
	m=getint();
	for (LL i=1;i<=m;i++){
		op=getint();
		if (op==1){
			x=getint(); y=getint(); p=getint(); q=getint(); if (fe&1){x^=ans; y^=ans;}
			change(1,1,100000,++tot,x,y,p,q);//区间是[1,100000] 
		}
		if (op==2){
			x=getint(); y=getint(); z=getint(); if (fe&1){x^=ans; y^=ans; z^=ans;}
			ans1=1; ans2=0; query(1,1,100000,x,y,z);
			ans=(LL)((LL)ans1*a[z]+ans2)%mo; printf("%lld\n",ans);
		}
	}
	
	return 0;
}