Card时间限制(普通/Java) : 5000 MS/ 10000 MS 运行内存限制 : 65536 KByte
总提交 : 169 测试通过 : 32 描述
YCC有一堆卡片，每张卡片上都写着一个正整数。YCC很喜欢将这些卡片排成一排，然后任意计算其中一段连续的卡片上数字的总和。随着年龄的增长，YCC觉得这个有点太容易了，于是他想出了以下两种操作： A．D a， 将第a张卡片从这些卡片中去掉。 B．S a b， 将第a张到第b张卡片上的数字的和计算出来。 当YCC想出这两个操作时候才发现自己搞不定，所以希望你能帮帮他计算出那些和。 输入
输入数据第一行为两个正整数N，M。表示有N张卡片和M个操作。 N, M <= 10^5 第二行为N个不大于10^5的正整数，按照卡片从左到右的顺序描述卡片上的数字。 随后的M行，每行均为操作A或者操作B，格式与题目描述相同。其中操作A与操作B中，卡片的编号均从0开始，并且数据保证不会出现违规数据。 输出： 对于每个操作B，输出该段的总和。每个输出占一行 输出
对于每个操作B，输出该段的总和。每个输出占一行 样例输入 3 5 样例输出 提示
6 5 3 题目来源 YCC |
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1012
树状数组练手题，主要是求第k大的数~~~~
虽然说树状数组能做的题，线段树都能做，但树状数组的精简还是有其优势的~~~
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=100100;
int n,m;
__int64 tree[maxn];
int num[maxn],s[maxn];
int fk(int k){
int i,now=0;
for(i=20;i>=0;i--){
now|=(1<<i);
if(now>=n || num[now]>=k)
now^=(1<<i);
else k-=num[now];
}
return now+1;
}
void add(int v,int v1,int v2){
while(v<=n){
tree[v]+=v2;
num[v]+=v1;
v+=v&-v;
}
}
__int64 query(int v){
__int64 sum=0;
while(v>0){
sum+=tree[v];
v-=v&-v;
}
return sum;
}
int main(){
int i,j;
char op[2];
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&s[i]);
add(i,1,s[i]);
}
while(m--){
scanf("%s",op);
if(op[0]=='S'){
scanf("%d%d",&i,&j);
if(i>j) swap(i,j);
printf("%I64d\n",query(fk(j+1))-query(fk(i+1)-1));
}
else{
scanf("%d",&i);
i=fk(i+1);
add(i,-1,-s[i]);
}
}
return 0;
}