清点人数

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 793 字

树状数组单点改前缀和

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1538
// 题意：n 节车厢，k 个事件：A m 问前 m 节车总学生数（m 单调不减）；B m p 第 m 节上 p 人；C m p 第 m 节下 p 人。学生总数≤1e5。
// 思路：树状数组单点加、前缀和。A m 即前缀和 [1,m]；B/C 在第 m 节 +p/-p。
// 复杂度：O(k log n) 时间 / O(n) 空间
// 易错点：车厢下标 1 基；A 查询的 m 保证不减但实现无需依赖；上下车直接修改对应位置。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int bit[MAXN];
int n;
void add(int i, int v){ for(;i<=n;i+=i&-i) bit[i]+=v; }
int sum(int i){ int s=0; for(;i>0;i-=i&-i) s+=bit[i]; return s; }
int main(){
    int k;
    if(!(cin>>n>>k)) return 0;
    while(k--){
        char op;
        cin>>op;
        if(op=='A'){
            int m; cin>>m;
            cout<<sum(m)<<"\n";
        }else{
            int m,p; cin>>m>>p;
            if(op=='B') add(m,p);
            else add(m,-p);
        }
    }
    return 0;
}

清点人数

正文

一本通·提高篇的其它内容