题意

题目链接

Sol

思路就是根据期望的线性性直接拿前缀和算贡献。。

这题输出的时候是不需要约分的qwq

如果你和我一样为了AC不追求效率的话直接#define int __int128就行了。。

代码十分清新

#include<bits/stdc++.h>

#define int __int128

using namespace std;

const int MAXN = 1e6 + 10;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

void print(int x) {

	if(x < 0) putchar('-'), x = -x;

    if (x > 9) print(x / 10);

    putchar('0' + x % 10);

}

int N, M, qwq, s[MAXN], a[MAXN], ans, Lim;

int get(int dep) {

	return 1 << (Lim - (dep - 1));

}

void Build(int l, int r, int dep, int sum) {

	ans += (a[r] - a[l - 1]) * get(dep);

	if(l == r) {s[l] = sum + get(dep); return ;}

	int mid = l + r >> 1;

	Build(l, mid, dep + 1, sum + get(dep));

	Build(mid + 1, r,dep + 1, sum + get(dep));

}

signed main() {

	N = read(); M = read(); qwq = read();

	for(int cur = 1; cur <= N; Lim ++, cur <<= 1);

	for(int i = 1; i <= N; i++) a[i] = read(), a[i] += a[i - 1];

	Build(1, N, 1, 0);

	for(int i = 1; i <= N; i++) s[i] += s[i - 1];

	while(M--) {

		int l = read(), r = read(), v = read();

		ans += ((s[r] - s[l - 1]) * v);

		print(((ans * qwq) >> Lim)); putchar('\n');

	}

	return 0;

}