luogu T96516 [DBOI2019]持盾 可持久化线段树+查分

因为题中的操作是区间加法，所以满足前缀相减性.

而每一次查询的时候还是单点查询，所以直接用可持久化线段树维护差分数组，然后查一个前缀和就行了.

code:

#include <bits/stdc++.h>

#define N 200004

#define LL long long

#define setIO(s) freopen(s".in","r",stdin)

using namespace std;

int n,m,q,tot,rt[N];

LL val[N];

int newnode() { return ++tot; }

struct node   { int ls,rs; LL sum;}t[N*50];

void build(int &now,int l,int r)

{

    now=newnode();

    if(l==r)   return ;

    int mid=(l+r)>>1;

    if(l<=mid)    build(t[now].ls,l,mid);

    if(r>mid)     build(t[now].rs,mid+1,r);

}

int update(int p,int l,int r,int pos,int v)

{

    int now=newnode();

    t[now]=t[p];

    t[now].sum=t[p].sum+1ll*v;

    if(l==r)  return now;

    int mid=(l+r)>>1;

    if(pos<=mid)    t[now].ls=update(t[p].ls,l,mid,pos,v);

    else t[now].rs=update(t[p].rs,mid+1,r,pos,v);

    return now;

}

LL query(int now,int l,int r,int L,int R)

{

    if(!now)   return 0;

    if(l>=L&&r<=R)  return t[now].sum;

    int mid=(l+r)>>1;

    LL re=0ll;

    if(L<=mid)  re+=query(t[now].ls,l,mid,L,R);

    if(R>mid)   re+=query(t[now].rs,mid+1,r,L,R);

    return re;

}

int main()

{

    // setIO("input");

    int i,j;

    scanf("%d%d%d",&n,&m,&q);

    for(i=1;i<=n;++i)   scanf("%lld",&val[i]);

    build(rt[0],1,n);

    for(i=1;i<=m;++i)

    {

        int l,r,h;

        scanf("%d%d%d",&l,&r,&h);

        rt[i]=update(rt[i-1],1,n,l,h);

        if(r<n)    rt[i]=update(rt[i],1,n,r+1,-h);

    }

    for(i=1;i<=q;++i)

    {

        int opt;

        scanf("%d",&opt);

        if(opt==1)

        {

            int x,y,z;

            scanf("%d%d%d",&x,&y,&z);

            LL L=query(rt[x-1],1,n,1,z);

            LL R=query(rt[y],1,n,1,z);

            printf("%lld\n",R-L+val[z]);

        }

        else

        {

            int pos,p;

            scanf("%d%d",&pos,&p);

            val[pos]=1ll*p;

        }

    }

    return 0;

}