比赛 数列操作练习题 评测结果 AAAAAAAAAAAAAAA
题目名称 数列操作A 最终得分 100
用户昵称 rvalue 运行时间 0.172 s
代码语言 C++ 内存使用 0.42 MiB
提交时间 2017-03-18 19:29:19
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int INF=0x7FFFFFFF;
const int MAXN=100010;

int n;
int m;
int a[MAXN];
int c[MAXN];

void Initialize();
int Query(int);
void Add(int,int);
void Build();
int LowBit(int);

int Main(){
	char buf[10];
	int from;
	int to;

	Initialize();
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		scanf("%s",buf);
		switch(buf[0]){
			case 'A':
				scanf("%d%d",&from,&to);
				Add(from,to);
			break;
			case 'S':
				scanf("%d%d",&from,&to);
				if(from>to)
					swap(from,to);
				printf("%d\n",Query(to)-Query(from-1));
			break;
		}
	}
	return 0;
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("shulie.in","r",stdin);
	freopen("shulie.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
	Build();
}

void Build(){
	for(int i=1;i<=n;i++)
		Add(i,a[i]);
}

int Query(int x){
	int ans=0;
	for(int i=x;i>0;i-=LowBit(i))
		ans+=c[i];
	return ans;
}

void Add(int x,int add){
	for(int i=x;i<=n;i+=LowBit(i))
		c[i]+=add;
}

inline int LowBit(int x){
	return x&-x;
}

int WORKING=Main();
int main(){;}