這個題屬于一個典型的區間維護題吧,有2個操作,
1、S x y 把第x個數改成y,
2、M x y 求出[x,y]區間所有數的和,
個人用樹狀數組做的,因為樹狀數組好寫點,還是 比較簡單~
代碼:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=400001;
int n,t[maxn];
int lowbit(int x)
{
return x&(-x);
}
long long sum(int x)
{
long long sum=0;
while(x>0)
{
sum+=t[x];
x-=lowbit(x);
}
return sum;
}
void Update(int x,int val)
{
while(x<=maxn)
{
t[x]+=val;
x+=lowbit(x);
}
}
int main()
{
int cas=1;
while(scanf("%d",&n)&&n)
{
memset(t,0,sizeof(t));
for(int i=1;i<=n;i++)
{
int ita;
scanf("%d",&ita);
Update(i,ita);
}
if(cas>1)
printf("\n");
printf("Case %d:\n",cas++);
while(1)
{
char op[10];
scanf("%s",op);
if(!strcmp(op,"END"))
break;
if(op[0]=='S')
{
int ita,itb;
scanf("%d%d",&ita,&itb);
long long val=sum(ita)-sum(ita-1);
Update(ita,itb-val);
}
else
{
int ita,itb;
scanf("%d%d",&ita,&itb);
printf("%lld\n",sum(itb)-sum(ita-1));
}
}
}
return 0;
}