In this HackerEarth Hacker with Team problem solution Alex has learnt many new concepts in hacking, and created his own team. He has N people (excluding Alex) in his team, where ith person has individual skill value Si where 1 <= i <= N. They are standing in a particular order, where person being the leftmost person and Nth person being the rightmost person.
Alex has found a special way to evaluate the contribution done by each person in the team. Contribution done by ith person (Ci) in the team can be calculated as sum of his skill value and the skill values of his K adjacent team members on the left side, where the value of K will be decided by Alex.
In case, there are not enough members on the left side, contribution will be equal to the sum of his skill value and the skill values of all the team members on the left side.
Alternatively,
Ci = Sigma(i,j=maximum(i-k,1))Sj
Alex can perform 2 types of operations now:
- He can write a program to calculate the total contribution done by all the team members in the range of l to r (both inclusive), where contribution of each person will be calculated using value of K decided by him.
- He can ask any person to change his skill value to X.
Being a great hacker, he is busy with other tasks, and needs your help in performing above operations.
HackerEarth Hacker with Team problem solution.
#include <cassert>
#include <cstdio>
int const N = 1234567;
void add(long long *f, int x, long long y) {
for (int i = x; i < N; i |= i + 1) {
f[i] += y;
}
}
long long get(long long *f, int x) {
long long ret = 0;
for (int i = x; i >= 0; i = (i & (i + 1)) - 1) {
ret += f[i];
}
return ret;
}
long long f[N], h[N];
int a[N];
int n;
long long getans(int x, int k) {
long long ans = get(f, x - k) * (long long) k;
ans += get(h, x) - get(h, x - k);
ans -= (get(f, x) - get(f, x - k)) * ((n - x - 1) - 1);
return ans;
}
int main() {
int q;
assert(2 == scanf("%d%d", &n, &q));
for (int i = 0; i < n; i++) {
assert(1 == scanf("%d", a + i));
add(f, i, a[i]);
add(h, i, (long long) a[i] * (n - i - 1));
}
for (int i = 0; i < q; i++) {
int op;
assert(scanf("%d", &op) == 1);
if (op == 1) {
int l, r, k;
assert(3 == scanf("%d%d%d", &l, &r, &k));
--l;
++k;
printf("%lldn", getans(r - 1, k) - getans(l - 1, k));
} else {
int x, y;
assert(2 == scanf("%d%d", &x, &y));
--x;
add(f, x, y - a[x]);
add(h, x, (long long) (y - a[x]) * (n - x - 1));
a[x] = y;
}
}
}