蛮有意思的一题……

考虑询问[tex]SS_i[/tex]，[tex][1,i][/tex]中的每个位置[tex]j[/tex]在答案中被计算的次数为[tex]i-j+1[/tex]，然后式子就可以变成这样：

[tex]\Sigma_{j=1}^{i} A[j]*(i-j+1)[/tex]

[tex](i+1)*\Sigma_{j=1}^{i} A[j]-\Sigma_{j=1}^{i} A[j]*j[/tex]

这样问题就简单多了，开两个树状数组乱搞搞即可。

代码：

/**************************************************************
    Problem: 3155
    User: danihao123
    Language: C++
    Result: Accepted
    Time:464 ms
    Memory:3164 kb
****************************************************************/
 
#include <cstdio>
#include <cstdlib>
const int maxn=100005;
typedef long long ll;
int n;
ll A[maxn];
ll C_1[maxn]; // 正常的BIT
inline int lowbit(int x){
    return x&(-x);
}
inline void add(int p,ll v){
    while(p<=n){
        C_1[p]+=v;
        p+=lowbit(p);
    }
}
inline ll sum(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_1[p];
        p-=lowbit(p);
    }
    return ans;
}
ll C_2[maxn]; // 累积的BIT
inline void add_2(int p,ll v){
    register int pos=p;
    while(pos<=n){
        C_2[pos]+=((ll)p)*v;
        pos+=lowbit(pos);
    }
}
inline ll sum_2(int p){
    register ll ans=0;
    while(p>0){
        ans+=C_2[p];
        p-=lowbit(p);
    }
    return ans;
}
 
int main(){
    int m,p;
    ll v;
    register int i;
    char *buf=(char*)calloc(10,1);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&A[i]);
        add(i,A[i]);
        add_2(i,A[i]);
    }
    while(m--){
        scanf("%s%d",buf,&p);
        if(buf[0]=='Q'){
            printf("%lld\n",((ll)p+1LL)*sum(p)-sum_2(p));
        }else{
            scanf("%lld",&v);
            add(p,v-A[p]);
            add_2(p,v-A[p]);
            A[p]=v;
        }
    }
    free(buf);
    return 0;
}

• 相关文章
• 全局相关文章