| Time Limit: 3 second(s) | Memory Limit: 32 MB |
The problem you need to solve here is pretty simple. You are give a function f(A, n), where A is an array of integers and n is the number of elements in the array. f(A, n) is defined as follows:
long long f( int A[], int n ) { // n = size of A
long long sum = 0;
for( int i = 0; i < n; i++ )
for( int j = i + 1; j < n; j++ )
sum += A[i] - A[j];
return sum;
}
Given the array A and an integer n, and some queries of the form:
1) 0 x v (0 ≤ x < n, 0 ≤ v ≤ 106), meaning that you have to change the value of A[x] to v.
2) 1, meaning that you have to find f as described above.
Input
Input starts with an integer T (≤ 5), denoting the number of test cases.
Each case starts with a line containing two integers: n and q (1 ≤ n, q ≤ 105). The next line contains n space separated integers between 0 and 106 denoting the array A as described above.
Each of the next q lines contains one query as described above.
Output
For each case, print the case number in a single line first. Then for each query-type "1" print one single line containing the value of f(A, n).
Sample Input |
Output for Sample Input |
|
1 3 5 1 2 3 1 0 0 3 1 0 2 1 1 |
Case 1: -4 0 4 |
Note
Dataset is huge, use faster I/O methods.
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<math.h>
6 #include<stdlib.h>
7 typedef long long LL;
8 LL bns[200000];
9 int main(void)
10 {
11 int k;
12 int i,j;
13 scanf("%d",&k);
14 int s;
15 int p,q;
16 LL ans=0;
17 for(s=1; s<=k; s++)
18 {
19 scanf("%d %d",&p,&q);
20 for(i=1; i<=p; i++)
21 {
22 scanf("%lld",&bns[i]);
23 }
24 ans=0;
25 for(i=1; i<=p; i++)
26 {
27 ans+=(LL)(p-2*i+1)*(LL)bns[i];
28 }
29 printf("Case %d:\n",s);
30 while(q--)
31 {
32 int ask;
33 int n,m;
34 scanf("%d",&ask);
35 if(ask==1)
36 {
37 printf("%lld\n",ans);
38 }
39 else
40 {
41 scanf("%d %d",&n,&m);
42
43 {
44 ans-=(LL)(p-2*(n+1)+1)*bns[n+1];
45 ans+=(LL)(p-2*(n+1)+1)*(LL)m;
46 bns[n+1]=m;
47 }
48 }
49 }
50 }
51 return 0;
52 }