Challenge 11

• 查看
• 提交
• 统计
• 提问

总时间限制: 

10000ms

 

单个测试点时间限制: 

1000ms

 

内存限制: 

262144kB

描述

给一个长为N的数列，有M次操作，每次操作是以下两种之一：

（1）修改数列中的一个数

（2）求某次操作后连续一段的和

输入

第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行，每行开头是一个字符，若该字符为‘M‘，则表示一个修改操作，接下来两个整数x和y，表示把x位置的数修改为y；若该字符为‘Q‘，则表示一个询问操作，接下来三个整数x、y、z，表示求数列中[x,y]这段区间在第z次操作后的和。

输出

对每一个询问操作单独输出一行，表示答案。

样例输入

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

样例输出

576

提示

1<=N<=10^5，1<=M<=10^5，输入保证合法，且所有整数及答案可用带符号32位整型存储。

可持久化线段树

鸣谢xxy学姐

#include<cstdio>#include<iostream>using namespace std;#define N 100001int n,m,cnt,ans;int root[N*20];int ls[N*20],sum[N*20],rs[N*20];int ope[N];void change(int l,int r,int &rt,int pre,int pos,int w){    if(!rt)rt=++cnt;    sum[rt]=sum[pre];    if(l==r){sum[rt]=w;return;}    int mid=(l+r)>>1;    if(pos<=mid)rs[rt]=rs[pre],change(l,mid,ls[rt],ls[pre],pos,w);    else ls[rt]=ls[pre],change(mid+1,r,rs[rt],rs[pre],pos,w);    sum[rt]=sum[ls[rt]]+sum[rs[rt]];}void query(int l,int r,int rt,int opl,int opr){    if(opl<=l&&opr>=r){        ans+=sum[rt];return ;    }    int mid=(l+r)>>1;    if(opl<=mid)query(l,mid,ls[rt],opl,opr);    if(opr>mid)query(mid+1,r,rs[rt],opl,opr);}int main(){    scanf("%d%d",&n,&m);    int x,y,z;    for(int i=1;i<=n;i++)    scanf("%d",&x),change(1,n,root[0],root[0],i,x);    char s[3];    int now=0;    for(int i=1;i<=m;i++)    {        ope[i]=now;        scanf("%s",s);        if(s[0]==‘M‘)        {            now++;            ope[i]=now;            scanf("%d%d",&x,&y);            change(1,n,root[now],root[now-1],x,y);        }        else         {            scanf("%d%d%d",&x,&y,&z);            ans=0;            query(1,n,root[ope[z]],x,y);            printf("%d\n",ans);        }    }    return 0;}