LOJ6346：线段树：关于时间 —

LOJ6346：线段树：关于时间 ——题解

阅读量：6856 次

发布时间：2019-06-26

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

老年选手困了30min后才想要推式子实在是太懒了……

我们可以对每次更新列表看成系数*x即可。

举例：第i次有列表(l,r,x)，则第j次求和时答案*(j-i)即可。

但是系数不统一很难受，于是得到：(i-k)*x=(i-1)*a，求a=x+(1-k)*x/(i-1)，则(i-1)*a=(i-1)*x+(1-k)*x

于是我们用线段树多维护一个(1-k)*x就行了。

注意一下线段树常数问题。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}ll b[N],tr[N*4],lz[N*4],t[N*4],lazy[N*4];inline void push(int a,int l,int r){ int mid=(l+r)>>1; lz[a<<1]+=lz[a];lz[a<<1|1]+=lz[a]; tr[a<<1]+=lz[a]*(mid-l+1);tr[a<<1|1]+=lz[a]*(r-mid); lz[a]=0; lazy[a<<1]+=lazy[a];lazy[a<<1|1]+=lazy[a]; t[a<<1]+=lazy[a]*(mid-l+1);t[a<<1|1]+=lazy[a]*(r-mid); lazy[a]=0;}void mdy(int a,int l,int r,int l1,int r1,ll w,bool on){ if(r
            
             
              >1; mdy(a<<1,l,mid,l1,r1,w,on);mdy(a<<1|1,mid+1,r,l1,r1,w,on); tr[a]=tr[a<<1]+tr[a<<1|1]; t[a]=t[a<<1]+t[a<<1|1];}ll qry(int a,int l,int r,int l1,int r1,ll k){ if(r
              
               
                >1; return qry(a<<1,l,mid,l1,r1,k)+qry(a<<1|1,mid+1,r,l1,r1,k);}int main(){ int n=read(); for(int i=1;i<=n;i++)b[i]=b[i-1]+read(); int m=read(); for(int i=1;i<=m;i++){ int d=read(); if(d==1){ int l=read(),r=read(),x=read(); mdy(1,1,n,l,r,x,0);mdy(1,1,n,l,r,(1-i)*x,1); }else{ int l=read(),r=read(); printf("%lld\n",b[r]-b[l-1]+qry(1,1,n,l,r,i-1)); } } return 0;}