(lightoj - 1369) answering queries (thinking)

Topic link ：Answering Queries - LightOJ 1369 - Virtual Judge

The question ： Definition f(A,n) yes Result , We have two operations , One is to query the current results , The other is to put A Modify the value of an element in the array

analysis ： We first find the result of the original array , Note that you cannot solve the result of the original array directly , This will time out , We can only observe the characteristics of each number to find the law to solve , such as a[i] Will act as n-i Secondary addend , And as a i-1 Times subtraction , So in general a[i] Will be added （n-2*i+1） Time , Using this law, we can o（n） Calculate the result of the original array ,    Let's analyze it a little bit What will be the impact of modifying an element on the result , For example a[x] yes m, Now change it to n, So for any containing a[x] The value of the expression of will change accordingly ,a[x] There are two ways in expressions , One is a[i]-a[x](i<x), The other is a[x]-a[j](j>x), The value of the former expression will increase m-n Yes x-1 This happens to expressions , The latter expression will reduce m-n, Yes n-x This happens to expressions , Generally speaking, there is an increase (2*x-n-1) individual (m-n), So we can o(1) The result was modified , Here is the code ：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N];
signed main()
{
	int T;
	cin>>T;
	for(int _=1;_<=T;_++)
	{
		printf("Case %lld:\n",_);
		long long ans=0;
		int n,q;
		scanf("%lld%lld",&n,&q);
		for(int i=1;i<=n;i++)
			scanf("%lld",&a[i]);
		for(int i=1;i<=n;i++)
			ans+=(n-2*i+1)*a[i];
		while(q--)
		{
			int op,x,y;
			scanf("%lld",&op);
			if(op==1) printf("%lld\n",ans);
			else
			{
				scanf("%lld%lld",&x,&y);
				x++;
				ans+=(a[x]-y)*(2*x-1-n);
				a[x]=y;
			}
		}
	}
	return 0;
}