牛客练习赛28(数据结构)

https://www.nowcoder.com/acm/contest/200/B
思路：比较经典的线段树模板题，事后学习了一下并且调了很久，主要是加法和乘法标记下传的问题，我们考虑同时如果同时存在两种标记，前一种标记必定是下传的最后一个区间（否则可以继续下传标记清空），但标记已经被写入，所以先乘后加是正确的选择，这种情况下不论先进行加法操作后进行乘法操作，或者先进行乘法操作后进行加法操作都可以得到正确的结果，最后注意整个维护的细节即可（初始化，标记下传等）。
代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e5+10;
long long a[maxn<<2],sum[maxn<<2],dousum[maxn<<2],maxv[maxn<<2],minv[maxn<<2];
long long mulzy[maxn<<2],addzy[maxn<<2];
int n,q;

inline void pushup(int o){
  sum[o] = sum[o<<1] + sum[o<<1|1];
  minv[o] = min(minv[o<<1],minv[o<<1|1]);
  maxv[o] = max(maxv[o<<1],maxv[o<<1|1]);
  dousum[o] = dousum[o<<1] + dousum[o<<1|1];
}

void pushdown(int o,int m){//先乘后加
    if(mulzy[o]!=1){
    dousum[o<<1]*=mulzy[o]*mulzy[o];;//因为要用的是原来的sum所以先计算平方和
    dousum[o<<1|1]*=mulzy[o]*mulzy[o];
    sum[o<<1] = mulzy[o]*sum[o<<1];
    sum[o<<1|1] = mulzy[o]*sum[o<<1|1] ;
    addzy[o<<1] = addzy[o<<1]*mulzy[o];
    addzy[o<<1|1] = addzy[o<<1|1]*mulzy[o];
    mulzy[o<<1] *=mulzy[o];
    mulzy[o<<1|1] *= mulzy[o];
    mulzy[o] = 1;
   }
   if(addzy[o]){
    dousum[o<<1]=dousum[o<<1]+2*addzy[o]*sum[o<<1]+addzy[o]*addzy[o]*(m-(m>>1));
    dousum[o<<1|1]=dousum[o<<1|1]+2*addzy[o]*sum[o<<1|1]+addzy[o]*addzy[o]*((m>>1));
    sum[o<<1] = sum[o<<1] + addzy[o]*(m-(m>>1));
    sum[o<<1|1] = sum[o<<1|1] + addzy[o]*(m>>1);
    addzy[o<<1] +=addzy[o];
    addzy[o<<1|1] += addzy[o];
    addzy[o] = 0;
   }
}

void build(int o,int l,int r){
  if(l<r){
    int mid = l+r>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    mulzy[o] = 1;//注意全部区间初始化为1
    pushup(o);
  }
  else{
    sum[o] = a[l];
    minv[o] = a[l];
    maxv[o] = a[l];
    dousum[o] = a[l]*a[l];
    mulzy[o] = 1;//注意全部区间初始化为1
    addzy[o] = 0;
  }
}

void add(int o,int tl,int tr,int l,int r,long long v){
  if(tr<l||r<tl)return;
  if(l<=tl&&tr<=r){
    dousum[o] = dousum[o] + 2*sum[o]*v + v*v*(tr-tl+1);
    addzy[o]+=v;
    sum[o]+=(tr-tl+1)*v;
        return;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  add(o<<1,tl,mid,l,r,v);
  add(o<<1|1,mid+1,tr,l,r,v);
  pushup(o);
} 

void mul(int o,int tl,int tr,int l,int r,long long v){
  if(tr<l||r<tl)return;
  if(l<=tl&&tr<=r){
    mulzy[o]*=v;
    addzy[o]*=v;
    sum[o]*=v;
    dousum[o]*=v*v;
        return;
  }
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  mul(o<<1,tl,mid,l,r,v);
  mul(o<<1|1,mid+1,tr,l,r,v);
  pushup(o);
} 

long long querysum(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return 0;
  if(l<=tl&&tr<=r)return sum[o];
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  long long ret = querysum(o<<1,tl,mid,l,r);
  ret+=querysum(o<<1|1,mid+1,tr,l,r);
  return ret;
}

long long querydousum(int o,int tl,int tr,int l,int r){
  if(tr<l||r<tl)return 0;
  if(l<=tl&&tr<=r)return dousum[o];
  pushdown(o,tr-tl+1);
  int mid = (tl+tr)>>1;
  long long ret = querydousum(o<<1,tl,mid,l,r);
  ret+=querydousum(o<<1|1,mid+1,tr,l,r);
  return ret;
}

int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
      scanf("%lld",&a[i]);
    }
    build(1,1,n);
    int num;
    int p,o;
    for(int i=1;i<=q;i++){
      scanf("%d%d%d",&num,&p,&o);
      if(num==1)printf("%lld\n",querysum(1,1,n,p,o));
      if(num==2)printf("%lld\n",querydousum(1,1,n,p,o));
      if(num==3){
        long long v;
        scanf("%lld",&v);
        mul(1,1,n,p,o,v);
      }
      if(num==4){
        long long v;
        scanf("%lld",&v);
        add(1,1,n,p,o,v);
      }
    }
  return  0;
}