官方题解

#include <bits/stdc++.h>
#define int long long

using namespace std;
int n, op, l, r, c;
int a[200000], b[200000], d[200000];
signed main() {
    cin >> n;
	int B = sqrt(n / 2);
    for (int i = 0; i < n; ++i) {
    	scanf("%lld", &a[i]);
		d[i / B] += a[i];
	}
    
    // 1 ~ n,  0 ~ n - 1
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &op);
        scanf("%lld %lld %lld", &l, &r, &c);
        if (op == 0) {
            l--, r--;
            for (; l % B != 0 && l <= r; l++) 
				a[l] += c, d[l / B] += c;
            for (; l + B - 1 <= r; l += B) 
				b[l / B] += c;
            for (; l <= r; ++l) 
				a[l] += c, d[l / B] += c;
        } else {
            l--, r--;
            int ans = 0;
            for (; l % B != 0 && l <= r; l++)  {
            	ans += a[l] + b[l / B];
            	ans %= (c + 1);
        	}
            for (; l + B - 1 <= r; l += B) {
            	ans += d[l / B] + b[l / B] * B;
            	ans %= (c + 1);
			}
            for (; l <= r; ++l) {
				ans += a[l] + b[l / B];
				ans %= (c + 1);
			}
			printf("%lld\n", ans);
        }
    }
    return 0;
}