牛客练习赛28B (经典)【线段树】

<题目链接>

qn姐姐最好了~

qn姐姐给你了一个长度为n的序列还有m次操作让你玩，

1 l r 询问区间[l,r]内的元素和

2 l r 询问区间[l,r]内的元素的平方 和

3 l r x 将区间[l,r]内的每一个元素都乘上x

4 l r x 将区间[l,r]内的每一个元素都加上x

输入描述:

第一行两个数n,m
接下来一行n个数表示初始序列
就下来m行每行第一个数为操作方法opt，
若opt=1或者opt=2，则之后跟着两个数为l,r
若opt=3或者opt=4，则之后跟着三个数为l,r,x
操作意思为题目描述里说的

输出描述:

对于每一个操作1,2，输出一行表示答案

输入

输出

备注:

对于100%的数据 n=10000,m=200000 (注意是等于号)

保证所有询问的答案在long long 范围内

解题分析：
本题主要的难点在于，对区间进行加或者乘上一个数后，如何快速的维护每个节点的sum 和pfh(区间所有数平方和) 值，如果仅仅是对区间的每个节点进行暴力单点更新的话，毫无疑问会超时。所以我们必须对区间整体修改，而且我们要想到，在区间的维度上，是可以对该区间的每个数平方和进行修改的，它并不像开根号一样，必须要下放到每个叶子节点，对具体的数进行开根。区间修改pfh值时，只需要利用平方和展开式，就能很容易的对区间平方和进行修改。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 #define Lson rt<<1,l,mid
  7 #define Rson rt<<1|1,mid+1,r
  8 typedef long long ll;
  9 const int M = 1e4+10;
 10 ll n,m,arr[M];
 11 struct Tree{
 12     ll sum,pfh,add,mul;
 13 }tr[M<<2];
 14 void Pushup(ll rt){
 15     tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
 16     tr[rt].pfh=tr[rt<<1].pfh+tr[rt<<1|1].pfh;  //pfh记录的是该区间所有元素的平方和
 17 }
 18 void Pushdown(ll rt,ll len){  //mul和add相当于两个lazy标记
 19     if(tr[rt].mul!=1){
 20         ll tmp=tr[rt].mul;
 21         tr[rt<<1].sum*=tmp,tr[rt<<1|1].sum*=tmp;
 22         tr[rt<<1].pfh=tr[rt<<1].pfh*tmp*tmp,tr[rt<<1|1].pfh=tr[rt<<1|1].pfh*tmp*tmp;  //相当于对该区间的每个数都进行平方
 23         tr[rt<<1].mul*=tmp,tr[rt<<1|1].mul*=tmp;  //这几个标记都要*mul
 24         tr[rt<<1].add*=tmp,tr[rt<<1|1].add*=tmp;
 25         tr[rt].mul=1;
 26     }
 27     if(tr[rt].add){
 28         ll tmp=tr[rt].add;
 29         tr[rt<<1].pfh=tr[rt<<1].pfh+2*tmp*tr[rt<<1].sum+tmp*tmp*(len-(len>>1)); //注意这里，要将更新pfh的语句放在更新sum的语句之前      
 30         tr[rt<<1|1].pfh=tr[rt<<1|1].pfh+2*tmp*tr[rt<<1|1].sum+tmp*tmp*(len>>1);
 31         tr[rt<<1].sum+=tmp*(len-(len>>1)),tr[rt<<1|1].sum+=tmp*(len>>1);    
 32         tr[rt<<1].add+=tmp,tr[rt<<1|1].add+=tmp;
 33         tr[rt].add=0;
 34     }
 35 }
 36 void build(ll rt,ll l,ll r){
 37     tr[rt].add=0,tr[rt].mul=1;
 38     if(l==r){
 39         tr[rt].sum=arr[l],tr[rt].pfh=arr[l]*arr[l];
 40         return;
 41     }
 42     ll mid=(l+r)>>1;
 43     build(Lson);
 44     build(Rson);
 45     Pushup(rt);
 46 }
 47 void update1(ll rt,ll l,ll r,ll L,ll R,ll c){
 48     if(L<=l&&r<=R){
 49         tr[rt].sum*=c,tr[rt].add*=c,tr[rt].mul*=c;
 50         tr[rt].pfh*=tr[rt].pfh*c*c;
 51         return;
 52     }
 53     Pushdown(rt,r-l+1);
 54     ll mid=(l+r)>>1;
 55     if(L<=mid)update1(Lson,L,R,c);
 56     if(R>mid)update1(Rson,L,R,c);
 57     Pushup(rt);
 58 }
 59 void update2(ll rt,ll l,ll r,ll L,ll R,ll c){
 60     if(L<=l&&r<=R){
 61         tr[rt].pfh=tr[rt].pfh+2*c*tr[rt].sum+c*c*(r-l+1);    //注意这里，要将更新pfh的语句放在更新sum的语句之前 
 62         tr[rt].add+=c;
 63         tr[rt].sum+=c*(r-l+1);    
 64         return;
 65     }
 66     Pushdown(rt,r-l+1);
 67     ll mid=(l+r)>>1;
 68     if(L<=mid)update2(Lson,L,R,c);
 69     if(R>mid)update2(Rson,L,R,c);
 70     Pushup(rt);
 71 }
 72 ll query(ll rt,ll l,ll r,ll L,ll R,ll ty){
 73     if(L<=l&&r<=R){
 74         if(ty==1)return tr[rt].sum;
 75         else return tr[rt].pfh;
 76     }
 77     Pushdown(rt,r-l+1);
 78     ll mid=(l+r)>>1;
 79     ll ans=0;
 80     if(L<=mid)ans+=query(Lson,L,R,ty);
 81     if(R>mid)ans+=query(Rson,L,R,ty);
 82     return ans;
 83 }
 84 int main(){
 85     scanf("%lld%lld",&n,&m);
 86         for(int i=1;i<=n;i++)scanf("%lld",&arr[i]);
 87         build(1,1,n);
 88         while(m--){
 89             ll op,x,y,c;
 90             scanf("%lld%lld%lld",&op,&x,&y);
 91             if(op==1||op==2){
 92                 printf("%lld
",query(1,1,n,x,y,op));
 93             }
 94             else{
 95                 scanf("%lld",&c);
 96                 if(op==3)update1(1,1,n,x,y,c);
 97                 else update2(1,1,n,x,y,c);
 98             }
 99         }
100     return 0;
101 }



2018-10-05