洛谷P3924 康娜的线段树(期望 前缀和)
程序员文章站
2022-03-10 09:49:06
题意 "题目链接" Sol 思路就是根据期望的线性性直接拿前缀和算贡献。。 这题输出的时候是不需要约分的qwq 如果你和我一样为了AC不追求效率的话直接 就行了。。 代码十分清新 ......
题意
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; }