A49458.统计……？ 题解

首先能想到的是，$B$ 没有修改，直接前缀和就能做。

考虑线段树维护区间 $A_i \times B_i$。如何维护？

push_up 的时候，一样的，不写了；

push_down 的时候，式子如下：

$$\sum_{i=l}^r (A_i+c) \times B_i \\ =\sum_{i=l}^r A_i \times B_i + c \times B_i \\ =(\sum_{i=l}^r A_i \times B_i) + (c\sum_{i=l}^r B_i)$$

加号前面是已知的，加号后面直接前缀和，$O(1)$ 计算。

然后写完了。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=5e5+55;
struct node{
    ll l,r,sum,tag;
};
ll n,q,op,l,r,c;
ll a[MAXN],b[MAXN],pre[MAXN];
node sgt[MAXN<<2];
inline void read(ll &x){
    x=0;
    bool neg=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch^'-') ch=getchar();
    if(ch=='-'){
        neg=true;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    if(neg) x*=-1;
    return;
}
inline void write(const ll &x){
    if(x<0){
        putchar('-');
        write(-x);
        return;
    }
    if(x<=9){
        putchar(x^48);
        return;
    }
    write(x/10);
    putchar(x%10^48);
    return;
}
#define ls(p) p<<1
#define rs(p) p<<1|1
inline void push_up(const ll &p){
    sgt[p].sum=sgt[ls(p)].sum+sgt[rs(p)].sum;
    return;
}
inline void build(const ll &l,const ll &r,const ll &p){
    sgt[p]={l,r,0,0};
    if(l>=r){
        sgt[p].sum=a[l]*b[l];
        return;
    }
    ll mid=l+r>>1;
    build(l,mid,ls(p));
    build(mid+1,r,rs(p));
    push_up(p);
    return;
}
inline void push_down(const ll &l,const ll &r,const ll &p){
    ll mid=l+r>>1;
    if(sgt[p].tag){
        sgt[ls(p)].sum+=(pre[mid]-pre[l-1])*sgt[p].tag;
        sgt[rs(p)].sum+=(pre[r]-pre[mid])*sgt[p].tag;
        sgt[ls(p)].tag+=sgt[p].tag;
        sgt[rs(p)].tag+=sgt[p].tag;
        sgt[p].tag=0;
    }
    return;
}
inline void update(const ll &l,const ll &r,const ll &ql,const ll &qr,const ll &p,const ll &c){
    if(l>=ql&&r<=qr){
        sgt[p].sum+=(pre[r]-pre[l-1])*c;
        sgt[p].tag+=c;
        return;
    }
    push_down(l,r,p);
    ll mid=l+r>>1;
    if(mid>=ql) update(l,mid,ql,qr,ls(p),c);
    if(mid<qr) update(mid+1,r,ql,qr,rs(p),c);
    push_up(p);
    return;
}
inline ll query(const ll &l,const ll &r,const ll &ql,const ll &qr,const ll &p){
    if(l>=ql&&r<=qr) return sgt[p].sum;
    push_down(l,r,p);
    ll res=0,mid=l+r>>1;
    if(mid>=ql) res+=query(l,mid,ql,qr,ls(p));
    if(mid<qr) res+=query(mid+1,r,ql,qr,rs(p));
    return res;
}
#undef ls
#undef rs
int main(){
    read(n);read(q);
    for(ll i=1;i<=n;i++) read(a[i]);
    for(ll i=1;i<=n;i++){
        read(b[i]);
        pre[i]=b[i]+pre[i-1];
    }
    build(1,n,1);
    while(q--){
        read(op);read(l);read(r);
        if(op==1){
            read(c);
            update(1,n,l,r,1,c);
        }
        else{
            write(query(1,n,l,r,1)/(pre[r]-pre[l-1]));
            puts("");
        }
    }
    return 0;
}