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

To the moon

10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 42 40 0C 1 1 1C 2 2 -1Q 1 2H 1 2 1

45591501

这一题和是一样的，唯一区别就是内存限制变小了，当然还有输出时多组数据之间不用空行。

于是，学到了一种函数式线段树成段更新时节约内存的办法 。。。

先考虑朴素的仅支持成段加减的线段树，我们可以用方式解决：

1.正常的懒惰标记，当访问到带有懒惰标记节点的子区间时将标记下传；

2.不用下传的懒惰标记，我们用一个标记来记录当前节点的整段区间被累加了多少，当询问的时候我们在从根节点走到目标结点的过程中不断累加所经过节点上的标记值。。。

基于这两种思想，就有了函数式线段树的两种实现方式，第一种在pushdown的过程中会产生大量的结点，而第二种没有pushdown的过程，不会新建过多的节点

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define rep(i,a,n) for (int i=a;i
          
           =a;i--)#define pb push_back#define fi first#define se secondtypedef vector
           
             VI;typedef long long ll;typedef pair
            
              PII;const int maxn=1e5+10;struct node{ int l,r; ll sum,add;}T[maxn*30];int root[maxn];int cnt;void pushup(int x){ T[x].sum=T[T[x].l].sum+T[T[x].r].sum;}int build(int l,int r){ int root=++cnt; T[root].add=0; if(l==r) { scanf("%lld",&T[root].sum); T[root].l=T[root].r=0; return root; } int m=(l+r)/2; T[root].l=build(l,m),T[root].r=build(m+1,r); pushup(root); return root;}void copy(int x,int y){ T[x].l=T[y].l; T[x].r=T[y].r; T[x].sum=T[y].sum; T[x].add=T[y].add;}int update(int root,int L,int R,int l,int r,int v){ int now=++cnt; copy(now,root); T[now].sum+=1ll*v*(r-l+1); if(L==l&&R==r) { T[now].add+=v; return now; } int m=(L+R)/2; if(r<=m) T[now].l=update(T[root].l,L,m,l,r,v); else if(l>m) T[now].r=update(T[root].r,m+1,R,l,r,v); else { T[now].l=update(T[root].l,L,m,l,m,v); T[now].r=update(T[root].r,m+1,R,m+1,r,v); } return now;}ll query(int root,int L,int R,int l,int r){ ll ans=0; if(L==l&&r==R) return T[root].sum; int m=(L+R)/2; ans+=(r-l+1)*T[root].add; if(r<=m) return ans+query(T[root].l,L,m,l,r); else if(l>m) return ans+query(T[root].r,m+1,R,l,r); else return ans+query(T[root].l,L,m,l,m)+query(T[root].r,m+1,R,m+1,r); return ans;}int main(){ int n,m; while(~scanf("%d%d",&n,&m)) { int now=0; cnt=0; root[now]=build(1,n); char op[5]; while(m--) { scanf("%s",op); int l,r,v; if(op[0]=='Q') { scanf("%d%d",&l,&r); printf("%lld\n",query(root[now],1,n,l,r)); } else if(op[0]=='C') { scanf("%d%d%d",&l,&r,&v); now++; root[now]=update(root[now-1],1,n,l,r,v); } else if(op[0]=='H') { scanf("%d%d%d",&l,&r,&v); printf("%lld\n",query(root[v],1,n,l,r)); } else if(op[0]=='B') scanf("%d",&v),now=v; } //puts(""); } return 0;}
            
           
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/fouzhe/article/details/56489113 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！