「SP11470」TTM - To the moon 解题报告

题面

解题思路

可持久化线段树

分析

这里只是提供可持久化线段树的板子，思想和主席树类似，每次对 $\log n$ 个点进行修改，这样就需要 $n\log n$ 的空间，因此写成结构体，大小开成 $80n$ ，反正只要不 $MLE$ 往大了开就好

struct node{
    int ls,rs;
    LL sum,tag;
}T[N*160];//80应该也是正确的

warning

要注意的地方是标记永久化，不仅要标记永久化，而且 $T[root].sum$ 的值也要做一定修改（比如 $root$ 这个区间完全包含修改区间的时候）

Code

#include<bits/stdc++.h>//大致上和主席树类似，emmm...貌似主席树就是可持久化线段树...
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 100003
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline LL read() {
    rll s=0,p=0;
    rgt char c=getchar();
    while(!isdigit(c)) p=(c=='-'),c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return p?-s:s;
}
inline void getc(char&c) {
    c=getchar();while(c<'A'||c>'Z') c=getchar();
}
struct node{
    int ls,rs;
    LL sum,tag;
}T[N*160];
int n,m,L,R,t,res,a[N],root[N];LL w,ans;
inline void built(rint k,rint l,rint r) {
    cmax(t,k);
    if(l==r) {T[k].sum=a[l];return;}
    rint m=(l+r)>>1,ls=k<<1;
    built(T[k].ls=ls,l,m),built(T[k].rs=ls|1,m+1,r),
    T[k].sum=T[ls].sum+T[ls|1].sum;
}
inline void Modify(rint l,rint r,rint &x,rint y) {
    if(r<L||R<l) return;
    x=++t,T[t]=T[y];
    if(L<=l&&r<=R) {T[x].tag+=w;return;}
    T[t].sum+=w*(min(r,R)-max(l,L)+1);//划重点，标记永久化的影响
    rint m=(l+r)>>1;
    Modify(l,m,T[x].ls,T[y].ls),
    Modify(m+1,r,T[x].rs,T[y].rs);
}
inline void push(rll tag,rint l,rint r) {
    ans+=(min(R,r)-max(L,l)+1)*tag;
}
inline void Query(rint l,rint r,rint root) {
    if(r<L||R<l) return;
    if(T[root].tag) push(T[root].tag,l,r);//划重点，标记永久化的影响
    if(L<=l&&r<=R) {ans+=T[root].sum;return;}
    rint m=(l+r)>>1;
    Query(l,m,T[root].ls),Query(m+1,r,T[root].rs);
}
int main()
{
    rint i;char op;
    n=read(),m=read();
    for(i=1;i<=n;i++) a[i]=read();
    built(1,1,n),root[0]=1;
    while(m--) {
        getc(op);
        if(op=='C') {
            L=read(),R=read(),w=read(),++res;
            Modify(1,n,root[res],root[res-1]);
        }
        else if(op=='Q')
            ans=0,L=read(),R=read(),Query(1,n,root[res]),printf("%lld\n",ans);
        else if(op=='H')
            ans=0,L=read(),R=read(),Query(1,n,root[read()]),printf("%lld\n",ans);
        else res=read();
    }
    return 0;
}