总时间限制: 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>
#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;
}
好吧是读入优化没判断负数