线段树+等差/等比-白红宇

线段树+等差/等比

阅读量：4993 次

发布时间：2019-06-12

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

等差：

https://www.luogu.org/problemnew/show/P1438

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
            8 #include 
            
              9 #include 
             
              10 #include 
              
               11 #include 
               
                12 #include 
                
                 13 #include 
                 
                  14 #include 
                  
                   15 #include 
                   
                    16 using namespace std;17 #define ll long long18 const int maxn=1e5+10;19 20 ll a[maxn<<2],u[maxn<<2],v[maxn<<2];21 22 void push_down(int ind,int len)23 {24 u[ind<<1]+=u[ind];25 v[ind<<1]+=v[ind];26 u[ind<<1|1]+=u[ind]+len*v[ind];27 v[ind<<1|1]+=v[ind];28 u[ind]=0;29 v[ind]=0;30 }31 32 void update(int ind,int l,int r,int x,int y,int k,int d)33 {34 if (x<=l && r<=y)35 {36 u[ind]+=k+d*(l-x);37 v[ind]+=d;38 return;39 }40 if (u[ind]!=0 || v[ind]!=0)41 push_down(ind,((r-l)>>1)+1);42 int m=(l+r)>>1;43 if (x<=m)44 update(ind<<1,l,m,x,y,k,d);45 if (m
                    
                     >1)+1);55 int m=(l+r)>>1;56 if (p<=m)57 query(ind<<1,l,m,p);58 else59 query(ind<<1|1,m+1,r,p);60 }61 62 int main()63 {64 int n,m,mode,x,y,p,i;65 ll k,d;66 scanf("%d%d",&n,&m);67 for (i=1;i<=n;i++)68 scanf("%lld",&a[i]);69 while (m--)70 {71 scanf("%d",&mode);72 if (mode==1)73 {74 scanf("%d%d%lld%lld",&x,&y,&k,&d);75 update(1,1,n,x,y,k,d);76 }77 else78 {79 scanf("%d",&p);80 printf("%lld\n",a[p]+query(1,1,n,p));81 }82 }83 return 0;84 }85 /*86 5 1087 1 2 3 4 588 1 2 5 1 289 2 590 1 3 4 -1 191 2 492 1 1 5 1 393 2 394 */

等比：

1 void push_down(int ind,int len)2 {3     u[ind<<1]+=u[ind];4     v[ind<<1]+=v[ind];5     u[ind<<1|1]+=u[ind]+pow(v[ind],len);6     v[ind<<1|1]+=v[ind];7     u[ind]=0;8     v[ind]=0;9 }

转载于:https://www.cnblogs.com/cmyg/p/9973707.html

你可能感兴趣的文章

jquery拖拽实现UI设计组件

查看>>

javamail模拟邮箱功能获取邮件内容-中级实战篇【内容|附件下载方法】（javamail API电子邮件实例）...