洛谷 U86564 排队形
题目背景
\(JDFZ2019\)秋季运动会开始辣！为了使强大的高一 · \(6\)班有一个更好的精神面貌，班主任\(T\)老师和体委\(LY\)，\(LYB\)开始排班级的队形......
题目描述
队形是一个不规则图形（要是规则的话还排什么），分为\(N\)列，每列有数量不定的同学（排队开始前每列都没有同学）。三个排队形的人有明确的分工：\(LY\)（代号为\(A\)）负责往队列中加人，\(LYB\)（代号为\(B\)）负责从队列中减去使队列不协调的人，而\(T\)老师（代号为\(C\)）只需要检查就可以了。排队开始后，他们会按时间顺序发出不同的指令（为了与其他人区别开，他们每个人发出指令前都会喊出自己的代号）：\(LY\)发出的指令中包括两个数\(M_1,K_1\)，表示第\(M_1\)列加入\(K_1\)位同学；\(LYB\)发出的指令中包括两个数\(M_2,K_2\)，表示第\(M_2\)列中删除\(K_2\)位同学；\(T\)老师发出的指令中也包括两个数\(P,Q\)，表示她现在想知道从第\(P\)列到第\(Q\)列的总人数。
输入格式
第一行有两个整数\(N,D\)，表示有\(N\)列，\(D\)个指令。
接下来有\(D\)行，每行开头先包括一个代号（\(A,B,C\)其中的一个），并按题目所述发出他/她的指令。
输出格式
输出行数与\(T\)老师的提问数相等，每行一个整数，回答\(T\)老师的问题。
样例输入
10 7
C 1 1
A 1 1
A 3 1
A 4 1
C 1 2
C 1 3
C 1 10
样例输出
0
1
2
3
提示：
数据范围：
对于30%的数据，\(1\le N,D\le 10^4\)，\(T\)老师至少提问\(1000\)次。
对于全部数据，\(1\le N,D\le 10^5\)，\(T\)老师至少提问\(30000\)次。
题解：
树状数组的题目。
我觉得应该算是裸题了，最后区间统计利用前缀和的思想就好。
代码：
#include<cstdio>
#include<iostream>
using namespace std;
int n,d;
int tree[500001];
void update(int x,int y)
{
for(int i=x;i<=n;i+=i&-i)
tree[i]+=y;
}
int query(int x)
{
int ret=0;
for(int i=x;i;i-=i&-i)
ret+=tree[i];
return ret;
}
int main()
{
//freopen("6.in","r",stdin);
//freopen("6.out","w",stdout);
scanf("%d%d",&n,&d);
while(d--)
{
char ch;
cin>>ch;
if(ch=='A')
{
int m,k;
scanf("%d%d",&m,&k);
update(m,k);
}
else if(ch=='B')
{
int m,k;
scanf("%d%d",&m,&k);
update(m,-k);
}
else if(ch=='C')
{
int p,q;
scanf("%d%d",&p,&q);
printf("%d\n",query(q)-query(p-1));
}
}
return 0;
}