代码：

#include <bits/stdc++.h>
using namespace std;
int id[50005], len;
// id 表示块的编号, len=sqrt(n) , 即上述题解中的s, sqrt的时候时间复杂度最优
long long a[50005], b[50005], s[50005];

// a 数组表示数据数组, b 数组记录每个块的整体赋值情况, 类似于 lazy_tag, s
// 表示块内元素总和
void add(int l, int r, long long x) {  // 区间加法
  int sid = id[l], eid = id[r];
  if (sid == eid) {  // 在一个块中
    for (int i = l; i <= r; i++) a[i] += x, s[sid] += x;
    return;
  }
  for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x;
  for (int i = sid + 1; i < eid; i++)
    b[i] += x, s[i] += len * x;  // 更新区间和数组(完整的块)
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
  // 以上两行不完整的块直接简单求和,就OK
}

long long query(int l, int r, long long p) {  // 区间查询
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {  // 在一个块里直接暴力求和
    for (int i = l; i <= r; i++) ans = (ans + a[i] + b[sid]) % p;
    return ans;
  }
  for (int i = l; id[i] == sid; i++) ans = (ans + a[i] + b[sid]) % p;
  for (int i = sid + 1; i < eid; i++) ans = (ans + s[i]) % p;
  for (int i = r; id[i] == eid; i--) ans = (ans + a[i] + b[eid]) % p;
  // 和上面的区间修改是一个道理
  return ans;
}
int main() {
  int n;
  cin >> n;
  len = sqrt(n);  // 均值不等式可知复杂度最优为根号n
  for (int i = 1; i <= n; i++) {  // 题面要求
    cin >> a[i];
    id[i] = (i - 1) / len + 1;
    s[id[i]] += a[i];
  }
  for (int i = 1; i <= n; i++) {
    int op, l, r, c;
    cin >> op >> l >> r >> c;
    if (op == 0)
      add(l, r, c);
    else
      cout << query(l, r, c + 1) << endl;
  }
  return 0;
}

oiwiki里直接复制粘贴的：(￣▽￣)"

我的分块已完全入土。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10,M=1010;
int a[N],s[M],tag[M],n,B;
void add(int l,int r,int x)
{
	int bl=(l-1)/B+1,br=(r-1)/B+1;
	if(bl==br)
	{
		for(int i=l;i<=r;i++)
			a[i]+=x,s[bl]+=x;
	}
	else
	{
		for(int i=l;i<=bl*B;i++)a[i]+=x,s[bl]+=x;
		for(int i=(br-1)*B+1;i<=r;i++)a[i]+=x,s[br]+=x;
		for(int i=bl+1;i<=br-1;i++)tag[i]+=x;
	}
}
int query(int l,int r,int P)
{
	int bl=(l-1)/B+1,br=(r-1)/B+1,ans=0;
	if(bl==br)
	{
		for(int i=l;i<=r;i++)
			ans=(ans+a[i]+tag[bl])%P;
	}
	else
	{
		for(int i=l;i<=bl*B;i++)ans=(ans+a[i]+tag[bl])%P;
		for(int i=(br-1)*B+1;i<=r;i++)ans=(ans+a[i]+tag[br])%P;
		for(int i=bl+1;i<br;i++)ans=(ans+s[i]+tag[i]*B)%P;
	}
	return ans;
}
signed main()
{
	cin>>n;B=sqrt(n);
	for(int i=1;i<=n;i++)cin>>a[i],s[(i-1)/B+1]+=a[i];
	for(int i=1;i<=n;i++)
	{
		int op,l,r,c;cin>>op>>l>>r>>c;
		if(op==0)add(l,r,c);
		else cout<<query(l,r,c+1)<<'\n';
	}
	return 0;
}

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e4 + 10, sqrtN = 250;
// 区间加，区间求和
// a[i]记录每个点的值，b[i]记录每个点i所在块;
// sum[i]记录第i个块的元素和（不含tag），tag[i]记录块内加法标记
// 每个块i的左端点L[i]、右端点R[i]
int n, a[N], b[N], L[sqrtN], R[sqrtN], tag[sqrtN], sum[sqrtN];

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int B = sqrt(n), cnt = (n + B - 1) / B; // B为每块的长度，cnt为总块数
    for (int i = 1; i <= n; i++) {
        b[i] = (i - 1) / B + 1;
    }
    for (int i = 1; i <= cnt; i++) {
        L[i] = (i - 1) * B + 1;
        R[i] = min(i * B, n);
        for (int j = L[i]; j <= R[i]; j++)
            sum[i] += a[j];
    }
    memset(tag, 0, sizeof(tag));
    for (int i = 1; i <= n; i++) {
        int op, l, r, c;
        cin >> op >> l >> r >> c;
        if (op == 0) {
            if (b[l] == b[r]) { // 如果l和r在同一块内
                for (int j = l; j <= r; j++)
                    a[j] += c;
                sum[b[l]] += (r - l + 1) * c;
            } else {
                for (int j = l; j <= R[b[l]]; j++)
                    a[j] += c;
                sum[b[l]] += (R[b[l]] - l + 1) * c;
                for (int j = b[l] + 1; j <= b[r] - 1; j++)
                    tag[j] += c;
                for (int j = L[b[r]]; j <= r; j++)
                    a[j] += c;
                sum[b[r]] += (r - L[b[r]] + 1) * c;
            }
        } else {
            int ans = 0, mod = c + 1;
            if (b[l] == b[r]) { // 如果l和r在同一块内
                for (int j = l; j <= r; j++)
                    ans = (ans + a[j] + tag[b[l]]) % mod;
            } else {
                for (int j = l; j <= R[b[l]]; j++)
                    ans = (ans + a[j] + tag[b[l]]) % mod;
                for (int j = b[l] + 1; j <= b[r] - 1; j++)
                    ans = (ans + sum[j] + tag[j] * (R[j] - L[j] + 1)) % mod;
                for (int j = L[b[r]]; j <= r; j++)
                    ans = (ans + a[j] + tag[b[r]]) % mod;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}