C++11(clang++ 3.9) 解法, 执行用时: 232ms, 内存消耗: 7652K, 提交时间: 2018-04-21 17:14:35

#include <cstdio>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;
long long s[N << 2], ss[N << 2], add[N << 2];
int n, q, c;

int inv(int x) {
	return x == 1 ? 1 : 1LL * inv(mod % x) * (mod - mod / x) % mod;
}

void build(int x, int l, int r) {
	if (l == r) {
		scanf("%lld", &s[x]);
		ss[x] = s[x] * s[x] - s[x];
		add[x] = 0;
		return;
	}
	int mid = l + r >> 1;
	build(x << 1, l, mid);
	build(x << 1 | 1, mid + 1, r);
	s[x] = s[x << 1] + s[x << 1 | 1];
	ss[x] = ss[x << 1] + ss[x << 1 | 1];
	add[x] = 0;
}

void get(int x, int l, int r, int v) {
	ss[x] = ss[x] + 2 * v * s[x] + (1LL * v * v - v) * (r - l + 1);
	s[x] = s[x] + 1LL * v * (r - l + 1);
	add[x] = add[x] + v;
}

void pd(int x, int l, int r) {
	int mid = l + r >> 1;
	get(x << 1, l, mid, add[x]);
	get(x << 1 | 1, mid + 1, r, add[x]);
	add[x] = 0;
}

long long change(int x, int l, int r, int ll, int rr, int v) {
	if (ll <= l&&r <= rr) {
		long long ans = ss[x];
		get(x, l, r, v);
		return ans;
	}
	if (add[x]) pd(x, l, r);
	int mid = l + r >> 1;
	long long s1 = 0, s2 = 0;
	if (ll <= mid) {
		s1 = change(x << 1, l, mid, ll, rr, v);
	}
	if (rr > mid) {
		s2 = change(x << 1 | 1, mid + 1, r, ll, rr, v);
	}
	s[x] = s[x << 1] + s[x << 1 | 1];
	ss[x] = ss[x << 1] + ss[x << 1 | 1];
	return s1 + s2;
}

int main() {
	while (~scanf("%d%d%d", &n, &c, &q)) {
		build(1, 1, n);
		int g = 1LL * inv(c) * inv(2) % mod;
		for (int i = 1; i <= q; i++) {
			int l, r, v;
			scanf("%d%d%d", &l, &r, &v);
			long long ans = change(1, 1, n, l, r, v) % mod;
			ans = ((1LL * c * c + c) % mod * (r - l + 1) % mod - ans) % mod;
			ans = (ans + mod) % mod * g % mod;
			printf("%lld\n", ans);
		}
	}
	return 0;
}