LightOJ 1369 Answering Queries(找规律)

题目链接：https://vjudge.net/contest/28079

题目大意：给你数组A[]以及如下所示的函数f:　　　　　

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;

}

有两个操作：0  x  v将A[x]转变成v。

　　　　　　1计算函数f的值

解题思路：①对于sum有规律：sum+=(n-1-2*i)*A[i]

　　　　　②每次改变数组元素的值时，直接把sum的值也改变

　　　　　③一定要记得强制转换long long,很重要

代码：

 #include<iostream>
 #include<cstdio>
 using namespace std;
 typedef long long LL;
 const int N=1e5+;
 int a[N]; int main(){
     int T;
     scanf("%d",&T);
     int cas=;
     while(T--){
         int n,q;
         scanf("%d%d",&n,&q);
         for(int i=;i<n;i++){
             scanf("%d",&a[i]);
         }
         printf("Case %d:\n",++cas);
         LL sum=;
         for(int i=;i<n;i++){
             sum+=(LL)(n--*i)*a[i];
         }
         while(q--){
             int op;
             scanf("%d",&op);
             if(op==){
                 printf("%lld\n",sum);
             }
             else{
                 int pos,v;
                 scanf("%d%d",&pos,&v);
                 //改变数组元素时，把sum也改变
                 sum-=(LL)(n-*pos-)*a[pos];
                 sum+=(LL)(n-*pos-)*v;
                 a[pos]=v;
             }
         }
     }
 }