洛谷P3924 康娜的线段树(期望 前缀和)

题意

题目链接

Sol

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

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

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

代码十分清新

代码语言：javascript复制

#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;
}

int 效率

0 人点赞