- 总时间限制:
- 10000ms
- 单个测试点时间限制:
- 1000ms
- 内存限制:
- 262144kB
- 描述
-
给一个长为N的数列，有M次操作，每次操作是以下两种之一：
（1）修改数列中的一个数
（2）求某次操作后连续一段的和
- 输入
- 第一行两个正整数N和M。
第二行N的整数表示这个数列。
接下来M行，每行开头是一个字符，若该字符为'M'，则表示一个修改操作，接下来两个整数x和y，表示把x位置的数修改为y；若该字符为'Q'，则表示一个询问操作，接下来三个整数x、y、z，表示求数列中[x,y]这段区间在第z次操作后的和。 - 输出
- 对每一个询问操作单独输出一行，表示答案。
- 样例输入
-
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
- 提示
- 1<=N<=10^5，1<=M<=10^5，输入保证合法，且所有整数及答案可用带符号32位整型存储。
- 可持久化线段树模板
-
#include<cstdio> #define N 100001 using namespace std; int n,m,cnt,ans; int root[N],lc[N*20],rc[N*20],sum[N*20]; int ope[N]; void change(int &k,int pre,int l,int r,int pos,int w) { if(!k) k=++cnt; sum[k]=sum[pre]; if(l==r) { sum[k]=w; return; } int mid=l+r>>1; if(pos<=mid) rc[k]=rc[pre],change(lc[k],lc[pre],l,mid,pos,w); else lc[k]=lc[pre],change(rc[k],rc[pre],mid+1,r,pos,w); sum[k]=sum[lc[k]]+sum[rc[k]]; } void query(int k,int l,int r,int opl,int opr) { if(l>=opl && r<=opr) { ans+=sum[k]; return; } int mid=l+r>>1; if(opl<=mid) query(lc[k],l,mid,opl,opr); if(opr>mid) query(rc[k],mid+1,r,opl,opr); } int main() { scanf("%d%d",&n,&m); int x,y,z; for(int i=1;i<=n;i++) scanf("%d",&x),change(root[0],root[0],1,n,i,x); int now=0; char s[3]; 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(root[now],root[now-1],1,n,x,y); } else { scanf("%d%d%d",&x,&y,&z); ans=0; query(root[ope[z]],1,n,x,y); printf("%d ",ans); } } }