题目连接
及其复杂，等我过了再写分析；OK，过了，来分析一下：

分析：

参考题解

首先这个题是区间查询，用前面写过的转化为差分写不了，sb了还调了好久…

首先手摸一下两个等差数列相加会发成什么？？
可以发现相加后还是等差数列，且首项是两个数列的叠加，公差也是叠加；
说明首项和公差是具有可加性的，这一点是线段树维护区间合并的关键；
所以我们线段树可以维护区间和，以及当前区间需要加的等差数列（首项，公差）

下面进行套路分析：

1. 维护什么东西？l,r,sum,k,d (k是首项，d是公差)

2. 如何维护？
   (1) pushup时：这个简单，区间和就行

   (2) pushdown时：（l是左子节点，r是右子节点，u是当前节点，wo(k,d,len)是求等差数列的和）

    l.k += u.k;
    l.d += u.d;
    l.sum += wo(u.k, u.d, (l.r - l.l + 1));
    
    r.k += (u.k + u.d*(l.r - l.l + 1));	//区间裂开，右边要加的等差数列的首项要变！
    r.d += u.d;
    r.sum = wo(u.k + u.d*(l.r - l.l + 1), u.d, (r.r - r.l + 1));
   
    u.k = u.d = 0;
   1
   2
   3
   4
   5
   6
   7
   8
   9

   (3) 打懒标记时：

    u.sum += wo(k, d, u.r - u.l + 1);
    u.d += d;
    u.k += k;
   1
   2
   3

3. 一些需要注意的点！！！
   (1) 由于我们update的加的是等差数列，当我们区间需要裂开时；
   即当前要修改区间与当前节点的左右子节点都有交集；
   显然此时左右两边要增加的等差数列是不同的（首项不同）；
   因此我们要换一种写法；

   (2) 注意这里的取模操作！
   我们粗略的算一下，把数据拉满：
   每次[1,2e5]都加上首项为1e9，公差为1e9的等差数列；
   那么每一次最后一个都加上末项2e14，2e5次操作显然是会爆longlong的；
   因此我们在计算的过程中就要一边取模；
   但是这个模数没给定，只是每次查询都给一个[3,25]的质数；
   那么我们可以把[3,25]中的质数的乘积当作固定的模数，记为mod；
   此时发现mod并不是一个质数了，而我们在计算的过程中要/2，即要求2的逆元；
   那么就不能用费马小定理了，用这个 inv2 = mod - mod/2;（长知识了！）

   (3)记得全开long long

代码：

#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<stdio.h>
#include<map>
#include<algorithm>
#include<deque>
#include<stack>
#include<set>
// #include 
#include<math.h>
#include<string.h>
#define IOS ios::sync_with_stdio(false),cin.tie(0);
using namespace std;
 
#define pb push_back
#define coutl cout<<"------------"<<endl;
#define fi first
#define se second
//#define long long int

#define ire(x) scanf("%d",&x)
#define iire(a,b) scanf("%d %d",&a,&b)
#define lre(x) scanf("%lld",&x)
#define llre(a,b) scanf("%lld %lld",&a,&b)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define endl "\n"
#define PI acos(-1.0)
#define int long long
typedef long long ll;
typedef unsigned long long ull;
      
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef pair<ll, ll> PLL;
typedef pair<double, double> PDD;
typedef pair<double, pair<int, double> > PDID;
typedef pair<char, char> PCC;
typedef pair<char, pair<int, int> > PCII;
typedef pair<int, pair<int, int> > PIII;
typedef pair<int, pair<int, pair<int, int> > > PIIII;
typedef pair<ll, pair<int, int> > PLII;

const int maxn = 2e5 + 7;
const int N = 1e6 + 7;
const int M = 1e6 + 7;
const int mod = 3*5*7*11*13*17*19*23;
const int inv = mod - mod/2;
const int inf = 0x3f3f3f3f;
 const ll INF = 0x3f3f3f3f3f3f3f3f;
const double pi = acos(-1);
const double eps = 1e-8;
  
ll gcd(ll a,ll b) {return b==0 ? a : gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b / gcd(a,b);}
ll qmi(ll a,ll b,ll p) {ll ans = 1; while(b) { if(b & 1) ans = ans * a % p; a = a * a % p; b >>= 1; } return ans;}
int lowbit(int x) {return x & (-x);}

int n,m;
int a[maxn];
struct node
{
	int l,r;
	int sum;	//区间和
	int k,d;	//首项，公差
}tr[maxn*4];

void pushup(int u)
{
	tr[u].sum = (tr[u<<1].sum + tr[u<<1|1].sum) % mod;
}

//求首项为k，公差为d，长度为len的等差数列和
int wo(int k,int d,int len)
{
	return (k*len%mod+(len-1)*len*inv%mod*d%mod)%mod;
}

void pushdown(int u)	//懒标记下传
{
	int k = tr[u].k;
	int d = tr[u].d;
	if(k && d)
	{
		tr[u<<1].k = (tr[u<<1].k + k) % mod;
		tr[u<<1].d = (tr[u<<1].d + d) % mod;
		tr[u<<1].sum = (tr[u<<1].sum + wo(k,d,tr[u<<1].r - tr[u<<1].l + 1)) % mod;
		
		tr[u<<1|1].k = (tr[u<<1|1].k + k + d*(tr[u<<1].r - tr[u<<1].l + 1)%mod) % mod;
		tr[u<<1|1].d = (tr[u<<1|1].d + d) % mod;
		tr[u<<1|1].sum = (tr[u<<1|1].sum + wo((k + d*(tr[u<<1].r - tr[u<<1].l + 1)%mod)%mod , d , tr[u<<1|1].r - tr[u<<1|1].l + 1));
		
		tr[u].k = tr[u].d = 0;
	}
}

void build(int u,int l,int r)	//建树
{
	if(l == r)
	{
		tr[u] = {l,r,a[l]%mod,0,0};
		return;
	}
	
	tr[u] = {l,r};
	
	int mid = l + r >> 1;
	build(u<<1, l, mid);
	build(u<<1|1, mid+1, r);
	
	pushup(u);
}

void update(int u,int l,int r,int k,int d)
{
	if(l > r) return;
	if(tr[u].l >= l && tr[u].r <= r)
	{
		tr[u].sum = (tr[u].sum + wo(k,d,tr[u].r - tr[u].l + 1));
		tr[u].d = (tr[u].d + d) % mod;
		tr[u].k = (tr[u].k + k) % mod;
		
		return;
	}
	
	pushdown(u);	//分裂了，下传懒标记
	
	int mid = tr[u].l + tr[u].r >> 1;
	if(r <= mid) update(u<<1, l, r, k,d);
	else if(l > mid) update(u<<1|1, l, r, k,d);
	else	//都有交集，要特判
	{
		update(u<<1, l, mid, k,d);
		k = (k + (ll)d*(mid-l+1)) % mod;
		update(u<<1|1, mid+1, r, k,d);
	}
	
	pushup(u);	//向上更新
}

ll query(int u,int l,int r)	//区间查询
{
	if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
	
	pushdown(u);	//分裂了，下传懒标记
	
	int mid = tr[u].l + tr[u].r >> 1;
	ll sum = 0;
	
	if(l <= mid) sum = (sum + query(u<<1, l, r)) % mod;
	if(r > mid) sum = (sum + query(u<<1|1, l, r)) % mod;
	
	return sum;
}

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	
	scanf("%lld",&m);
	while(m--)
	{
		int op;
		scanf("%lld",&op);
		
		if(op == 1)
		{
			int l,r;
			int k,d;
			scanf("%lld %lld",&l,&r);
			scanf("%lld %lld",&k,&d);
			
			k %= mod;
			d %= mod;
			
			update(1,l,r,k,d);
		}
		else
		{
			int l,r,p;
			scanf("%lld %lld",&l,&r);
			scanf("%lld",&p);
			
			ll ans = query(1,l,r) % p;
			
			cout<<ans<<'\n';
		}
	}
	
	return 0;
}
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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194