测试一下博客

集训队出的题目，网上没有题解，于是写一个自己的思路

想让博客变得和涛涛一样

题意：

思路：

因为询问求和，所以肯定要让ai*ki维护成一个整体才能相加，不然如果分开，区间取到ai*ki且i是维护一个区间的时候得到的值就有误了。因为此时的值应该是al*kl+a(l+1)*k(l+2)+.......+ar*kr而不是现在维护的（al+a(l+1)+...ar)*(kl+k(l+1)+...kr)，因为分开维护会导致把a或k看成整体，而不是a*k。

所以维护ai*ki，单独在结构体定义一个sum，我们发现，当a区间+w的时候，sum其实变化的就是+(k*w），k区间加的时候同理，所以只要在pushdown里额外加一个对sum的传递就好了，详细见代码。

代码

半年前的码风，看个思路就行啦。

#include <bits/stdc++.h>
//#define int long long
#define CIO std::ios::sync_with_stdio(false)
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
#define pii pair<int,int>
using namespace std;
const int N=2e5+5;
struct tree{
    int a,k,sum;
}tr[4*N];
int num[N],laza[4*N],lazk[4*N];
void builda(int p,int l,int r){
    if (l==r){
        tr[p].a=num[l];
        return;
    }
    int mid=l+r>>1;
    builda(2*p,l,mid);
    builda(2*p+1,mid+1,r);
    tr[p].a=tr[2*p].a+tr[2*p+1].a;
}
void buildk(int p,int l,int r){
    if (l==r){
        tr[p].k=num[l];
        tr[p].sum=tr[p].k*tr[p].a;
        return;
    }
    int mid=l+r>>1;
    buildk(2*p,l,mid);
    buildk(2*p+1,mid+1,r);
    tr[p].k=tr[2*p].k+tr[2*p+1].k;
    tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void pushdown(int p,int l,int r){
    int mid=l+r>>1;
    laza[2*p]+=laza[p];
    laza[2*p+1]+=laza[p];
    tr[2*p].sum+=laza[p]*tr[2*p].k;
    tr[2*p+1].sum+=laza[p]*tr[2*p+1].k;
    tr[2*p].a+=laza[p]*(mid-l+1);
    tr[2*p+1].a+=laza[p]*(r-mid);
    lazk[2*p]+=lazk[p];
    lazk[2*p+1]+=lazk[p];
    tr[2*p].sum+=lazk[p]*tr[2*p].a;
    tr[2*p+1].sum+=lazk[p]*tr[2*p+1].a;
    tr[2*p].k+=lazk[p]*(mid-l+1);
    tr[2*p+1].k+=lazk[p]*(r-mid);
    lazk[p]=0;
    laza[p]=0;
}
int query(int p,int l,int r,int x,int y){
    if (x<=l&&r<=y){
        return tr[p].sum;
    }
    pushdown(p,l,r);
    int mid=l+r>>1,ans=0;
    if (x<=mid)ans+=query(2*p,l,mid,x,y);
    if (mid<y)ans+=query(2*p+1,mid+1,r,x,y);
    return ans;
}
void updatea(int p,int l,int r,int x,int y,int w){
    if (x<=l&&r<=y){
        tr[p].sum+=w*tr[p].k;
        tr[p].a+=w*(r-l+1);
        laza[p]+=w;
        return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if (x<=mid)updatea(2*p,l,mid,x,y,w);
    if (mid<y)updatea(2*p+1,mid+1,r,x,y,w);
    tr[p].a=tr[2*p].a+tr[2*p+1].a;
    tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void updatek(int p,int l,int r,int x,int y,int w){
    if (x<=l&&r<=y){
        tr[p].sum+=w*tr[p].a;
        tr[p].k+=w*(r-l+1);
        lazk[p]+=w;
        return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if (x<=mid)updatek(2*p,l,mid,x,y,w);
    if (mid<y)updatek(2*p+1,mid+1,r,x,y,w);
    tr[p].k=tr[2*p].k+tr[2*p+1].k;
    tr[p].sum=tr[2*p].sum+tr[2*p+1].sum;
}
void work(){
    int n,q;
    cin>>n>>q;
    rep(i,1,n){
        cin>>num[i];
    }
    builda(1,1,n);
    rep(i,1,n){
        cin>>num[i];
    }
    buildk(1,1,n);
    int op,l,r,w;
    rep(i,1,q){
        cin>>op;
        if (op==1){
            cin>>l>>r>>w;
            updatea(1,1,n,l,r,w);
        }
        else if (op==2){
            cin>>l>>r>>w;
            updatek(1,1,n,l,r,w);
        }
        else{
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
}
signed main(){
    CIO;
    work();
    return 0;
}

总结：

一道好的线段树板子练习题

哭哭，没备份误删了一次，咕咕...