nefuoj 1212线段树区间更新-白红宇

nefuoj 1212线段树区间更新

阅读量：4205 次

发布时间：2019-05-26

本文共 2152 字，大约阅读时间需要 7 分钟。

还是序列求和

Problem:1212

Time Limit:1000ms

Memory Limit:65535K

Description

有一个长度为n的全0序列，然后你需要完成以下三个操作，1 u v val将u到v的值全部增加val，2 u v val将u到v的值全部设为val，3 u v求u到v的和

Input

多组数据，每组输入n和q（1<=n,q<=100000），接下来n个数（保证每个数为小于1000大于0），然后q个操作与上述描述一致

Output

对于第三个操作，我们需要输出它的和（数据保证和不会大于10的9次方）

Sample Input

5 61 1 4 23 1 52 2 3 93 1 52 1 5 33 1 5

Sample Output

822 15 #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int inf=0x3f3f3f3f;const int maxn=100010;int num[maxn<<2],flag1[maxn<<2],flag2[maxn<<2];void pushup(int node){    num[node]=num[node<<1]+num[node<<1|1];}void pushdown(int node,int m){    if(flag2[node]>=0){        flag2[node<<1]=flag2[node<<1|1]=flag2[node];        flag1[node<<1]=flag1[node<<1|1]=0;        num[node<<1]=flag2[node]*(m-(m>>1));        num[node<<1|1]=flag2[node]*(m>>1);        flag2[node]=-1;    }    if(flag1[node]){        flag1[node<<1]+=flag1[node];flag1[node<<1|1]+=flag1[node];        num[node<<1]+=flag1[node]*(m-(m>>1));        num[node<<1|1]+=flag1[node]*(m>>1);        flag1[node]=0;    }}void buildtree(int le,int ri,int node){    flag1[node]=0;    flag2[node]=-1;    if(le==ri){        num[node]=0;        return ;    }    int t=(le+ri)>>1;    buildtree(le,t,node<<1);    buildtree(t+1,ri,node<<1|1);    pushup(node);}void update(int l,int r,int val,int op,int le,int ri,int node){    if(l<=le&&ri<=r){        if(op==1){            flag1[node]+=val;            num[node]+=val*(ri-le+1);        }else{            flag1[node]=0;flag2[node]=val;            num[node]=val*(ri-le+1);        }        return ;    }    pushdown(node,ri-le+1);    int t=(le+ri)>>1;    if(l<=t) update(l,r,val,op,le,t,node<<1);    if(r>t) update(l,r,val,op,t+1,ri,node<<1|1);    pushup(node);}int query(int l,int r,int le,int ri,int node){    if(l<=le&&ri<=r) return num[node];    pushdown(node,ri-le+1);    int t=(le+ri)>>1,ans=0;    if(l<=t) ans+=query(l,r,le,t,node<<1);    if(r>t) ans+=query(l,r,t+1,ri,node<<1|1);    return ans;}int main(){    int n,q,val,op,u,v;    while(scanf("%d%d",&n,&q)!=-1){        buildtree(1,n,1);        for(int i=0;i