清点人数

第一行两个整数n,k，表示火车共有n节车厢以及k个事件。
接下来有k行，按时间先后给出k个事件，每行开头都有一个字母A，B或C。

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

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

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

学生总人数不会超过 $10^5$ 。

C++14(g++5.4) 解法, 执行用时: 206ms, 内存消耗: 39904K, 提交时间: 2020-05-04 14:18:19

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int n,k;
int tre[N];
int lowbit(int x)
{
	return x&-x;
}
int getsum(int x)
{
	int ans=0;
	for(int i=x;i>=1;i-=lowbit(i))
		ans+=tre[i];
	return ans;
}
void update(int x,int y)
{
	for(int i=x;i<=n;i+=lowbit(i))
		tre[i]=tre[i]+y;
}
int main()
{
	scanf("%d%d",&n,&k);
	memset(tre,0,sizeof(tre)); 
	while(k--)
	{
		char ch;
		int a,b;
		cin>>ch;
		if(ch=='A')
		{
			scanf("%d",&a);
			printf("%d\n",getsum(a));
		}else
		if(ch=='B')
		{
			scanf("%d%d",&a,&b);
			update(a,b);
		}else
		if(ch=='C')
		{
			scanf("%d%d",&a,&b);
			update(a,-b);
		}
	}
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 182ms, 内存消耗: 836K, 提交时间: 2023-07-11 00:00:16

#include "bits/stdc++.h"
using namespace std;
int a[500009],sum[500009],n;
void add(int x,int y){
	for(;x<=n;x+=(x&-x))
		a[x]+=y;
}
int ppp(int x){
	int s=0;
	for(;x>=1;x-=(x&-x))
		s+=a[x];
	return s;
}
int main(){
	int q;
	cin>>n>>q;
	char c;
	while(q--)
	{
		cin>>c;
		int x,y;
		if(c=='A')
		{
			cin>>x;
			printf("%d\n",ppp(x));
		}
		else if(c=='B')
		{
			cin>>x>>y;
			add(x,y);
		}
		else
		{
			cin>>x>>y;
			add(x, -y);
		}	
	}
}

详情