(未完待续)
题目链接:Vijos P1320/LibreOJ 10116/信息学奥赛一本通 T1538。
题目
题目描述
NK 中学组织同学们去五云山寨参加社会实践活动,按惯例要乘坐火车去。由于 NK 中学的学生很多,在火车开之前必须清点好人数。
初始时,火车上没有学生。当同学们开始上火车时,年级主任从第一节车厢出发走到最后一节车厢,每节车厢随时都有可能有同学上下。年级主任走到第 $m$ 节车厢时,他想知道前 $m$ 节车厢上一共有多少学生,但是他没有调头往回走的习惯。也就是说每次当他提问时,$m$ 总会比前一次大。
题解
思路
树状数组:
- 对于操作
A
,我们执行printf("%d\n",T.Query(m));
- 对于操作
B
,我们执行T.Update(m,p);
- 对于操作
C
,我们执行T.Update(m,-p);
代码
代码实现很简单。
#include<cstdio>
//以上为头文件
const int MAXN=500000+5;//最大数据范围
const int MAXK=100000+5;//最大数据范围
struct TreeArray{//树状数组模板
#define lowbit(x) ( (x) & ( - (x) ) )
int n,unit[MAXN];
void Update(int ID,int val){
while(ID<=n){
unit[ID]+=val;
ID+=lowbit(ID);
}
return;
}
int Query(int ID){
register int sum=0;
while(ID){
sum+=unit[ID];
ID-=lowbit(ID);
}
return sum;
}
#undef lowbit
};
char str[4];
int n,k;
TreeArray T;
int main(void){
register int i;
scanf("%d%d",&n,&k);
T.n=n;//赋值
for(i=1;i<=k;++i){//操作
static int m,p;
scanf("%s%d",str,&m);
if(str[0]=='A')
printf("%d\n",T.Query(m));
else{
scanf("%d",&p);
if(str[0]=='B')
T.Update(m,p);
if(str[0]=='C')
T.Update(m,-p);
}
}
return 0;
}
近期评论