HDU 4348 To the moon （主席树区间更新）-白红宇

HDU 4348 To the moon （主席树区间更新）

阅读量：5911 次

发布时间：2019-06-19

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

题意：首先给你n个数，开始时间为0，最后按照操作输出

给你四种操作：

1. C l r d : 在（l，r）区间都加上d，时间加一

2. Q l r : 询问现在（l，r）的区间和

3. H l r t : 询问在t的时间（l，r）的区间和

4. B t : 直接回到t的时间

题解：首先是区间修改区间查询，可以想到线段树，接着就是询问历史版本与回到历史版本，这样就是主席树了

首先我们知道普通主席树是单点修改，并支持历史版本的区间求和与回到历史版本（就是这删除之后的树），仅仅只是因为它存了多棵线段树

而我们这儿是要进行区间修改，所以第一反应就是模拟线段树的lazy标记，并在查询时再更新再建树，但是这样会卡空间

因此我们需要这样想，模拟lazy标记进行重建树（最多建立2*log2（n）个节点）是必须的，但是查询时就不需要重建树了

这样我们就需要记录两个值：sum代表这一段中被增加区间的与此这一段的区间相交的总和，com代表这一段都需要增加这么多

这时我们查询时就需要每次加上com与待查询的区间相交的值（加上之前更新的），最后再包含的区间里加上sum再减去这儿com与待查询的区间相交的值（重复了）

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  using namespace std;#define eps 1E-8/*注意可能会有输出-0.000*/#define Sgn(x) (x<-eps? -1 :x
                  
                    0.0 ? x+eps : x-eps)//浮点数转化#define zero(x) (((x)>0?(x):-(x))
                   
                    >b)typedef long long ll;typedef unsigned long long ull;const int Inf=1<<28;const ll INF=1ll<<60;const double Pi=acos(-1.0);const int Mod=1e9+7;const int Max=1e5+7;int root[Max],tot;struct node{ int lef,rig; ll sum,com;//相交总共的和 这一段每个点都加上这个}msegtr[Max*40];ll pre[Max];//把原来的数放入前缀和里，主席树里仅仅更新修改的值void Init(int &cnt){ cnt=0; msegtr[0].lef=msegtr[0].rig=0; msegtr[0].sum=msegtr[0].com=0ll; root[0]=0,tot=0; pre[0]=0ll; return;}int Jud(int sta,int enn,int lef,int rig)//关键的区间交{ return max(min(rig,enn)-max(lef,sta)+1,0);}void Create(int sta,int enn,int &x,int y,int lef,int rig,int com){ msegtr[++tot]=msegtr[y]; msegtr[tot].sum+=(ll)com*Jud(sta,enn,lef,rig); x=tot; if(sta>=lef&&enn<=rig)//模拟线段树区间更新 { msegtr[tot].com+=com;//这一段每个点都加上这个 return; } int mid=dir(sta+enn,1); if(mid>=lef) Create(sta,mid,msegtr[x].lef,msegtr[y].lef,lef,rig,com); if(mid
                    
                     =lef&&enn<=rig) { return msegtr[x].sum-msegtr[x].com*Jud(sta,enn,lef,rig);//多加了，要减去 } int mid=dir(sta+enn,1); ll ans=0ll; if(mid>=lef) { ans+=Query(sta,mid,msegtr[x].lef,lef,rig)+msegtr[msegtr[x].lef].com*Jud(sta,mid,lef,rig);//加上区间交的值 } if(mid

转载于:https://www.cnblogs.com/zhuanzhuruyi/p/5933760.html

你可能感兴趣的文章