I'm trying to solve this problem.
My logic is as follows :
Say input array is : 7,4,5,6
Then the value of F[A] will be
7*7 + 4*4 - 2*7*4 +
7*7 + 5*5 - 2*7*5 +
7*7 + 6*6 - 2*7*6 +
4*4 + 5*5 - 2*5*4 +
4*4 + 6*6 - 2*4*6 +
5*5 + 6*6 - 2*5*6
Thus, F[A] will be
3*(7*7) + 3*(4*4) + 3*(5*5) + 3*(6*6) - 2* ( 7*(4 + 5 + 6) + 4*(5 + 6) + 5*(6) )
To calculate this, first prepare the sum array where sum[i] is sum of all the elements of a from i to length of array
for(int i=n-1;i>=0;i--) {
if(i == n-1) {
sum[i] = a[i];
} else {
sum[i] = sum[i+1] + a[i];
}
}
Then to calculate F[A],
double ans = 0;
for(int i=0;i<n;i++) {
ans += a[i] * a[i] * (n - 1);
if(i != n - 1) {
ans -= (2 * a[i] * sum[i+1]);
}
ans %= MOD;
}
That will be the F[A] for the original input array.
For query type 1,x,v
For example we have 1,2,8
The array will be 7,8,5,6
The previous ans was:
3*(7*7) + 3*(4*4) + 3*(5*5) + 3*(6*6) - 2 * ( 7*(4 + 5 + 6) + 4*(5 + 6) + 5*(6) )
The new ans will be :
3*(7*7) + 3*(8*8) + 3*(5*5) + 3*(6*6) - 2 * ( 7*(8 + 5 + 6) + 8*(5 + 6) + 5*(6) )
Re writing it,
3*(7*7) + 3*(8*8) + 3*(5*5) + 3*(6*6) - 2 * ( 8 * ( 7 + 5 + 6 ) + 7 * ( 5 + 6 ) + 5 * (6) )
To incorporate such change in O(1),
I have one variable totalSum which has the value of sum[0] or sum of all the elements in the array
The code to make changes is:
//Undoing the effects of a[x] from F[A]
ans -= a[x] * a[x] * (n - 1);
ans += 2 * a[x] * ( totalSum- a[x] );
//Making changes in total sum and actual a[x]
totalSum += (-a[x] + v);
a[x] = v;
//Incorporating the changes as explained above
ans += a[x] * a[x] * (n - 1);
ans -= 2 * a[x] * ( totalSum - a[x] );
ans %= MOD;
Similarly for query type 2,x,v
//Undoing the effects of a[x] from F[A]
ans -= a[x] * a[x] * (n - 1);
ans += 2 * a[x] * ( totalSum- a[x] );
//Making changes in total sum and actual a[x]
totalSum += v
a[x] += v;
//Incorporating the changes as explained above
ans += a[x] * a[x] * (n - 1);
ans -= 2 * a[x] * ( totalSum - a[x] );
ans %= MOD;
I'm getting correct answers in my custom inputs. I have tried cross checking the answers with the randomly generated input and calculating them using brute force ( O(n*2) ) and the logic explained above. And I am getting correct answer for each custom input.
Although, I get wrong answer when I submit the problem. Any idea why ?
Here is the full code I'm submitting
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
class Main {
private static final double MOD = Double.parseDouble("2760727302517");
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
final int t = Integer.parseInt(br.readLine());
for(int Q=1;Q<=t;Q++) {
bw.write("Case "+Q+":\n");
String ip[] = br.readLine().split(" ");
final int n = Integer.parseInt(ip[0]);
final int q = Integer.parseInt(ip[1]);
final double a[] = new double[n];
final double sum[] = new double[n];
ip = br.readLine().split(" ");
for(int i=0;i<n;i++) {
a[i] = Double.parseDouble(ip[i]);
}
for(int i=n-1;i>=0;i--) {
if(i == n-1) {
sum[i] = a[i];
} else {
sum[i] = sum[i+1] + a[i];
}
}
double ans = 0;
double totalSum = sum[0];
for(int i=0;i<n;i++) {
ans += a[i] * a[i] * (n - 1);
if(i != n - 1) {
ans -= (2 * a[i] * sum[i+1]);
}
ans %= MOD;
}
for(int T=0;T<q;T++) {
final String query[] = br.readLine().split(" ");
if(query.length == 1) {
bw.write(String.format("%.0f\n",ans%MOD));
} else {
final int tmp = Integer.parseInt(query[0]);
final int x = Integer.parseInt(query[1]) - 1;
final double v = Double.parseDouble(query[2]);
ans -= a[x] * a[x] * (n - 1);
ans += 2 * a[x] * ( totalSum- a[x] );
if(tmp == 1) {
totalSum += (-a[x] + v);
a[x] = v;
} else {
totalSum += v;
a[x] += v;
}
ans += a[x] * a[x] * (n - 1);
ans -= 2 * a[x] * ( totalSum - a[x] );
ans %= MOD;
}
}
}
bw.close();
}
}
