[SP11460]TTM - To the moon

摘要

题意:可持久化区间修改查询。 .

标记永久化

在主席树上做区间查询,标记持久化。主席树直接维护序列区间和。做修改的时侯,我们对 log 个区间的结点打标记,但是不下传。查询的时侯,遇到路径上标记就累加对应标记的信息。相当于我们做了标记就不再去动这个标记,所以叫作标记永久化。这不是本文的重点。

差分法

考虑普通的区间修改查询。用树状数组的差分方法

于是我们维护两个主席树,主席树维护区间和,一个维护 ,一个维护 . 查询的时侯查询前缀和即可。另外,同一对指针数组可以维护多个主席树(因为主席树只与上个版本有关)

码短。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=1e5+5;
int n,m;

const int SZ=1<<24;
int tot;
int lc[SZ],rc[SZ],sum[SZ];
int r1[N+M],r2[N+M];

int modify(int pos,int v,int u,int l=1,int r=n){int u2=++tot,mid=(l+r)>>1;
    sum[u2]=sum[u]+v, lc[u2]=lc[u],rc[u2]=rc[u];
    if(l==r)return u2;
    if(pos<=mid)lc[u2]=modify(pos,v,lc[u],l,mid);
    else rc[u2]=modify(pos,v,rc[u],mid+1,r);
    return u2;
}
int query(int pos,int u,int l=1,int r=n){//pos 的前缀和
    if(r<=pos||l==r)return sum[u];
    int mid=(l+r)>>1;
    if(pos<=mid)return query(pos,lc[u],l,mid);
    else return sum[lc[u]]+query(pos,rc[u],mid+1,r);
}

int a[N];
int pre(int pos,int u1,int u2){
    return a[pos]+(pos+1)*query(pos,u1)-query(pos,u2);
}

signed main(){
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]), a[i]+=a[i-1];
    char op[5];
    int l,r,d,t=0;//t 是当前时间戳
    for(int i=1;i<=m;i++){scanf("%s",op);
        if(op[0]=='C'){scanf("%lld%lld%lld",&l,&r,&d);
            ++t;// 更新时间戳
            r1[t]=modify(r+1,-d, modify(l,d,r1[t-1]));
            r2[t]=modify(r+1,-d*(r+1), modify(l,d*l,r2[t-1]));
        }else if(op[0]=='Q'){scanf("%lld%lld",&l,&r);
            printf("%lld\n",pre(r,r1[t],r2[t])-pre(l-1,r1[t],r2[t]));
        }else if(op[0]=='H'){scanf("%lld%lld%lld",&l,&r,&d);
            printf("%lld\n",pre(r,r1[d],r2[d])-pre(l-1,r1[d],r2[d]));
        }else scanf("%lld",&t);
    }
    return 0;
}

 上一篇
NOI2005 维护数列 NOI2005 维护数列
摘要 题意:维护一个数列支持 6 种操作:在某一位置插入 / 删除 / 覆盖 / 翻转 / 求和一段数字;求整个数列的最大的连续一段的数字的和。 既然这个序列的形态变化,自然想到平衡树维护。然后,我就调了 6 小时 emmm 打覆盖和翻转
2019.05.21
下一篇 
FHQ Treap 入门 FHQ Treap 入门
2019.9.19 编入精选文章。 摘要 整整四个月的沉寂,四个月的恐惧自闭,就在最后的 6 个小时,在凌晨 12 点 48 分,他醒了!扼住了平衡树的咽喉 emmm(手动滑稽) FHQ Treap | Treap | Splay大概讲一
2019.05.18
  目录