这道题是树状数组+数学题，然而我数学并不好

题目描述

对于一个长度为nn的序列a1,a2,a3……ana1,a2,a3……an，其前缀和（Prefix Sum）SiSi为前ii个元素的和，即∑k=1iai∑k=1iai。而前缀和的前缀和（Preprefix Sum）就是把前缀和序列S1,S2,S3……SnS1,S2,S3……Sn作为原序列，再求一次前缀和。记再次求得的前缀和序列的第ii位为SSiSSi。 现在给定一个长度为nn的序列a1,a2,a3……ana1,a2,a3……an，有两种操作：

Modify i x

将的值改为；

Query i

询问SSiSSi的值。

请编写一个程序来实现这两种操作。

 

输入格式

第一行有两个整数nn和mm，分别表示序列长度和操作个数。 接下来的一行有nn个整数，即给定的序列a1,a2,a3……ana1,a2,a3……an。 接下来有mm行，每行对应一个操作，格式见题目描述。

输出格式

对于每个询问操作，输出一行，表示所询问的SSiSSi的值。

样例一

input

5 31 2 3 4 5Query 5Modify 3 2Query 5

output

3532

样例解释

进行了修改操作之后，序列变为{

1,2,3,4,5}{1,2,3,4,5},对应的前缀和序列为{

1,3,5,9,14}{1,3,5,9,14},故SS5=32SS5=32。

限制与约定

对于30%的数据,1≤n,m≤1001≤n,m≤100

对于70%的数据,1≤n,m≤10001≤n,m≤1000

对于100%的数据,1≤n,m≤100000,且在任意时刻都有0≤ai≤1000001≤n,m≤100000,且在任意时刻都有0≤ai≤100000

时间限制：1s1s

空间限制：256MB

首先这道题一看就是个树状数组，别问我怎么看出来的

然后便是开心的推结论时间

num: a1 ,a2 ,a3 ,a4

prefix: a1 ,a1+a2, a1+a2+a3

i*prefix: a1 ,2*a1+2*a2 ,3*a1+3*a2+3*a3(2)

preprefix: a1 ,2*a1+a2 ,3*a1+2*a2+a3(1)

(2)-(1): 0*a1 ,0*a1+a2 ,0*a1+a2+2*a3(3)

我们要求的就是(1)=(2)-(3);

(2)很明显是前缀和，用一个树状数组就能处理，

(3)很明显是(i-1)*ai的前缀和，再用一个树状数组维护

还有一点，就是要开longlong！！要开longlong！！要开longlong！！

不开longlong见祖宗，多年OI一场空

然后就A了

1 #include
     
       2 #include
      
        3 #include
       
         4 #define lowbit(a) a&(-a) 5 using namespace std; 6 typedef long long ll; 7 ll n,m,x,y; 8 ll tree1[101111],tree2[101111],num[101111]; 9 char opt[10];10 void add(ll pos,ll val,ll op)11 {12     switch(op)13     {14         case 1:15             for(int i=pos;i<=n;i+=lowbit(i))16                 tree1[i]+=val;17             break;18         case 2:19             for(int i=pos;i<=n;i+=lowbit(i))20                 tree2[i]+=val;21             break;22     }23     24 }25 ll ask(ll pos,ll op)26 {27     ll ans=0;28     switch(op)29     {30         case 1:31             for(int i=pos;i;i-=lowbit(i))32                 ans+=tree1[i];33             break;34         case 2:35             for(int i=pos;i;i-=lowbit(i))36                 ans+=tree2[i];37             break;38     }39     return ans;40 }41 int main()42 {43     scanf("%lld%lld",&n,&m);44     for(int i=1;i<=n;i++)45         scanf("%lld",&num[i]),46         add(i,num[i],1),add(i,num[i]*(i-1),2);47     for(int i=1;i<=m;i++)48     {49         scanf("%s",opt);50         if(opt[0]=='M')51         {52             scanf("%lld%lld",&x,&y); 53             add(x,y-num[x],1);54             add(x,(y-num[x])*(x-1),2);55             num[x]=y;56         }else if(opt[0]=='Q')57         {58             scanf("%lld",&x);59             ll xx=x*ask(x,1),yy=ask(x,2);60             printf("%lld\n",x*ask(x,1)-ask(x,2));61         }62     }63     return 0;64 }