题解 P8165 [eJOI2021] AddK

· · 题解

更逊的阅读体验

不知道为什么这道题还没有题解。

Solution

对于操作 1，由于 K\le 10，直接暴力单点修改即可。
而操作 2 的询问，不难发现，最后结果的呈现形式是

1\times A_l+2\times A_{l+1}+3\times A_{l+2}+\ldots+3\times A_{r-2}+2\times A_{r-1}+1\times A_r

其中中间可能有一段系数均为 m 的项。那么为了维护这样的形式，我们不仅要维护 \sum A_i，还要维护 \sum i\times A_i，这样 1\times A_l+2\times A_{l+1}+3\times A_{l+2}+\ldots 就可以变为 \sum\limits_{i=l}^{l+m-1}i\times A_i -(l-1)\times\sum\limits_{i=l}^{l+m-1}A_i 而直接计算了。

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int n,K,Q,t[11];
ll a[N],sum[N<<2],isum[N<<2];
void pushup(int u){sum[u]=sum[u<<1]+sum[u<<1|1],isum[u]=isum[u<<1]+isum[u<<1|1];}
void build(int u,int l,int r){
    if(l==r)return sum[u]=a[l],isum[u]=1ll*l*a[l],void();
    int mid=(l+r)/2;
    build(u<<1,l,mid);build(u<<1|1,mid+1,r);
    pushup(u);
}
void upd(int p,ll k,int u=1,int l=1,int r=n){
    if(l==r)return sum[u]=k,isum[u]=1ll*l*k,void();
    int mid=(l+r)/2;
    p<=mid?upd(p,k,u<<1,l,mid):upd(p,k,u<<1|1,mid+1,r);
    pushup(u);
}
ll ask(ll *S,int p,int q,int u=1,int l=1,int r=n){
    if(p>q)return 0;
    if(p<=l&&r<=q)return S[u];
    int mid=(l+r)/2;ll res=0;
    if(p<=mid)res+=ask(S,p,q,u<<1,l,mid);
    if(q>mid)res+=ask(S,p,q,u<<1|1,mid+1,r);
    return res;
}
int main(){
    scanf("%d%d",&n,&K);
    for(int i=1;i<=n;i++)scanf("%lld",a+i);
    build(1,1,n);
    scanf("%d",&Q);
    for(int T=1,o;T<=Q;T++){
        scanf("%d",&o);
        if(o==1){
            for(int i=1;i<=K;i++)scanf("%d",t+i);
            ll at1=a[t[1]];
            for(int i=1;i<K;i++)upd(t[i],a[t[i]]=a[t[i+1]]);
            upd(t[K],a[t[K]]=at1);
        }else{
            ll l,r,m;
            scanf("%lld%lld%lld",&l,&r,&m);
            int len=r-l+1;ll res=0;
            if(len<m){puts("0");continue;}
            else if(len==1){printf("%lld\n",ask(sum,l,r));continue;}
            res=m*ask(sum,l,r);
            res+=ask(isum,l,l+m-1)-(l+m-1)*ask(sum,l,l+m-1);
            res+=(r-m+1)*ask(sum,r-m+1,r)-ask(isum,r-m+1,r);
            printf("%lld\n",res);
        }
    }
    return 0;
}