清点人数-白红宇

清点人数

阅读量：7117 次

发布时间：2019-06-28

本文共 1434 字，大约阅读时间需要 4 分钟。

问题 D: 清点人数

时间限制: 1 Sec 内存限制: 128 MB

提交: 16 解决: 9

[] [] [] [命题人:]

题目描述

NK中学组织同学们去五云山寨参加社会实践活动，按惯例要乘坐火车去。由于NK中学的学生很多，在火车开之前必须清点好人数。

初始时，火车上没有学生。当同学们开始上火车时，年级主任从第一节车厢出发走到最后一节车厢，每节车厢随时都有可能有同学上下。年级主任走到第m节车厢时，他想知道前m节车厢上一共有多少学生，但是他没有调头往回走的习惯。也就是说每次当他提问时，m总会比前一次大。

输入

第一行两个整数n,k，表示火车共有n节车厢以及k个事件。

接下来有k行，按时间先后给出k个事件，每行开头都有一个字母A，B或C。

如果字母为A，接下来是一个数m，表示年级主任现在在第m节车厢；

如果字母为B，接下来是两个数m,p，表示在第m节车厢有p名学生上车；

如果字母为C，接下来是两个数m,p，表示在第m节车厢有p名学生下车。

学生总人数不会超过10

⁵。

输出

对于每个A，输出一行，一个整数，表示年级主任的问题的答案。

样例输入

复制样例数据

10 7A 1B 1 1B 3 1B 4 1A 2A 3A 10

样例输出

提示

对于全部数据，1≤n≤5×10⁵,1≤k≤10⁵。

解题思路：裸的树状数组查询，修改。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #define REP(i, a, b) for(int i = (a); i <= (b); ++ i)#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)#define PER(i, a, b) for(int i = (a); i >= (b); -- i)using namespace std;const int maxn = 1e7 + 5;int n, k,p[maxn];int lowbit(int a) { return a & (-a);}int sum(int a) { int val=0; while (a) val += p[a], a -= lowbit(a); return val;}void update(int a,int w) { while (a<=n)p[a] += w,a+=lowbit(a);}int main(){ cin >> n>>k; int cur,z; while (k--) { char q; cin >> q>>cur; if (q == 'A') { cout << sum(cur) << endl; } else if (q == 'B') { cin >> z; update(cur, z); } else { cin >> z; update(cur, -z); } }}

转载于:https://www.cnblogs.com/czy-power/p/10357659.html

你可能感兴趣的文章