牛客练习赛28 B数据结构（线段树）

阳光穿透心脏的1/2处 2021-09-30 06:02 214阅读 0赞

链接：[https://www.nowcoder.com/acm/contest/200/B][https_www.nowcoder.com_acm_contest_200_B]  
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒  
 空间限制：C/C++ 262144K，其他语言524288K  
 64bit IO Format: %lld

## 题目描述  ##

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，输出一行表示答案

示例1

## 输入 ##

复制

5 6
    1 2 3 4 5
    1 1 5
    2 1 5
    3 1 2 1
    4 1 3 2
    1 1 4
    2 2 3

## 输出 ##

复制

15
    55
    16
    41

## 备注: ##

对于100%的数据 n=10000,m=200000 (注意是等于号)
    
    保证所有询问的答案在long long 范围内
    
    解题思路：这题目就是纯粹考查代码能力，板子没记牢，就因为下推少了个+号和*号就一直WA，他妈竟然样例竟然又能过，比赛一结束竟然就发现了，一提交就AC了，真是要气死了。。。
    思路就是这样，复制下出题人的题解吧。
    显然，线段树
    窝们记录4个东西，区间和tree[root][0]，区间平方和 tree[root][1]，乘法懒标记 add2[root]，加法懒标记add1[root] 。
    查询的话就是常规查询，打标记就是线段树2板子一样，
    初值：add1[root]=0,add2[root]=1;
    加法：add1[root]+=dx
    乘法：add2[root]*=dx;
    然后考虑更新答案
    当前区间[l,r] ，当前节点root,这里面每个元素都变成了( a[i]为更新后, x[i]为更新前)

![1396791-20181005224856045-798017797.png][]

所以

![1396791-20181005224928544-1169077106.png][]

然后就标准线段树板子

#include<iostream> #include<cstdio> #include<cstring>
    using namespace std; #define maxn 10005
    #define lson l,mid,root<<1
    #define rson mid+1,r,root<<1|1
    long long n,m,tree[maxn<<2][2],add1[maxn<<2],add2[maxn<<2]; void pushup(long long root) { tree[root][0]=tree[root<<1][0]+tree[root<<1|1][0]; tree[root][1]=tree[root<<1][1]+tree[root<<1|1][1]; } void pushdown1(long long l,long long r,long long root) { //加法下推
        if(add1[root]) { add1[root<<1]+=add1[root];  //+号不能少，切记
            add1[root<<1|1]+=add1[root]; long long x=tree[root<<1][0]; long long y=tree[root<<1|1][0]; tree[root<<1][0]+=l*add1[root]; tree[root<<1|1][0]+=r*add1[root]; tree[root<<1][1]+=2*x*add1[root]+l*add1[root]*add1[root]; tree[root<<1|1][1]+=2*y*add1[root]+r*add1[root]*add1[root]; add1[root]=0; } } void pushdown2(long long l,long long r,long long root) { //乘法下推
        if(add2[root]!=1) { add2[root<<1]*=add2[root];  //*号不能少，切记
            add2[root<<1|1]*=add2[root]; tree[root<<1][0]*=add2[root]; tree[root<<1|1][0]*=add2[root]; tree[root<<1][1]*=add2[root]*add2[root]; tree[root<<1|1][1]*=add2[root]*add2[root]; add2[root]=1; } } void build(long long l,long long r,long long root) { add1[root]=0; add2[root]=1; if(l==r) { scanf("%lld",&tree[root][0]); tree[root][1]=tree[root][0]*tree[root][0]; return; } long long mid=(l+r)>>1; build(lson); build(rson); pushup(root); } void update1(long long L,long long R,long long C,long long l,long long r,long long root) { //加法更新
        if(L<=l&&r<=R) { long long x=tree[root][0]; tree[root][0] += (r-l+1)*C; tree[root][1] += 2*x*C+(r-l+1)*C*C; add1[root] += C; return ; } long long mid = (l+r)/2; pushdown2(mid-l+1,r-mid,root); pushdown1(mid-l+1,r-mid,root); if(L<=mid) update1(L,R,C,lson); if(R>mid) update1(L,R,C,rson); pushup(root); } void update2(long long L,long long R,long long C,long long l,long long r,long long root) { //乘法更新
        if(L<=l&&r<=R) { tree[root][0] *= C; tree[root][1] *= C*C; add2[root] *= C; if(add1[root]) add1[root] *= C; return ; } long long mid = (l+r)/2; pushdown2(mid-l+1,r-mid,root); pushdown1(mid-l+1,r-mid,root); if(L<=mid) update2(L,R,C,lson); if(R>mid) update2(L,R,C,rson); pushup(root); } long long query(long long L,long long R,long long c,long long l,long long r,long long root) { if(L<=l&&R>=r) { if(c==1) return tree[root][0]; if(c==2) return tree[root][1]; } long long ans=0,mid=(l+r)>>1; pushdown2(mid-l+1,r-mid,root); pushdown1(mid-l+1,r-mid,root); if(L<=mid) ans+=query(L,R,c,lson); if(R>mid) ans+=query(L,R,c,rson); return ans; } int main() { cin>>n>>m; build(1,n,1); while(m--) { long long op,x,y,val; scanf("%lld",&op); if(op==1||op==2) { scanf("%lld%lld",&x,&y); printf("%lld\n",query(x,y,op,1,n,1)); } else if(op==3||op==4) { scanf("%lld%lld%lld",&x,&y,&val); if(op==3) update2(x,y,val,1,n,1); else update1(x,y,val,1,n,1); } } return 0; }

转载于:https://www.cnblogs.com/zjl192628928/p/9746241.html

[https_www.nowcoder.com_acm_contest_200_B]: https://www.nowcoder.com/acm/contest/200/B
[1396791-20181005224856045-798017797.png]: /images/20210725/98f994ff47114c448ceeb849025947be.png
[1396791-20181005224928544-1169077106.png]: /images/20210725/9fef7c13bd9a4102b0a40ca854830565.png