（未完待续）

题目链接：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;
}