15:Challenge 11（主席树裸题）

5 4
1 2 3 4 5
Q 2 3 0
M 3 5
Q 2 3 2
Q 1 3 1

5
7
6

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN=2000001;
const int mod=998244353;
inline void read(int &n)
{
    //char c='+';bool flag=0;n=0;
    //while(c<'0'||c>'9') c=='-'?flag=1,c=getchar():c=getchar();
    //while(c>='0'&&c<='9') n=n*10+c-48,c=getchar();
    scanf("%d",&n);
}
struct node
{
    int ls,rs,sum;
    node(){ls=rs=sum=0;}
}tree[MAXN];
int how;
int root[MAXN];
int cz[MAXN];
int ans=0;
int tot=0;
void update(int k)
{
    tree[k].sum=tree[tree[k].ls].sum+tree[tree[k].rs].sum;
}
void change(int l,int r,int &k,int pre,int pos,int val)
{
    if(!k)    k=++tot;
    tree[k].sum=tree[pre].sum;
    if(l==r)
    {
        tree[k].sum=val;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid)    tree[k].rs=tree[pre].rs,change(l,mid,tree[k].ls,tree[pre].ls,pos,val);
    else tree[k].ls=tree[pre].ls,change(mid+1,r,tree[k].rs,tree[pre].rs,pos,val);
    update(k);
}
void query(int l,int r,int k,int wl,int wr)
{
    if(wl<=l&&r<=wr)
    {    ans+=tree[k].sum;
        return ;    }
    int mid=(l+r)>>1;
    if(wl<=mid)    query(l,mid,tree[k].ls,wl,wr);
    if(wr>mid)    query(mid+1,r,tree[k].rs,wl,wr);
}
int main()
{
    int n,m;
    read(n);read(m);
    for(int i=1;i<=n;i++)
    {
        read(how);
        change(1,n,root[0],root[0],i,how);
    }
    int now=0;
    for(int i=1;i<=m;i++)
    {    
        cz[i]=now;
        char s[3];
        scanf("%s",s);
        if(s[0]=='M')// 修改 
        {
            now++;cz[i]=now;
            int pos,val;read(pos);read(val);
            change(1,n,root[now],root[now-1],pos,val);
        }
        else
        {
        
            int ll,rr,tim;
            read(ll);read(rr);read(tim);
            ans=0;
            query(1,n,root[cz[tim]],ll,rr);
            printf("%d\n",ans);
        }
    }
    return 0;
}