求条P4879（玄关）

#include <bits/stdc++.h>
using namespace std;
int n,m,num[100005],block,belong[100005],cnt[320];
long long ans;
bool vis[100005];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	block = sqrt(n);
	if (block == 0) block = 1;
	for (int i = 1;i <= n;i++)
	{
		cin >> num[i];
		belong[i] = (i - 1) / block;
		cnt[belong[i]]++;
		ans += num[i];
	}
	int total_blocks = (n + block - 1) / block;
	for (int i = 1;i <= m;i++)
	{
		char opt;
		cin >> opt;
		if (opt == 'C')
		{
			int x,y;
			cin >> x >> y;
			if (!vis[x])
			{
				num[x] -= y;
				ans -= y;				
			}
		}
		if (opt == 'I')
		{
			int x,y;
			cin >> x >> y;
			if (vis[x])
			{
				cnt[belong[x]]++;
				vis[x] = 0;
			}
			else
			{
				ans -= num[x];
			}
			num[x] = y;
			ans += num[x];
		}
		if (opt == 'D')
		{
			int x,y = -1,j = 0;
			cin >> x;
			while (j < total_blocks)
			{
				if (x <= cnt[j])
				{
					break;
				}
				x -= cnt[j];
				j++;
			}
			for (int k = j * block + 1;k <= min((int)((j + 1) * block), n);k++)
			{
				if (!vis[k])
				{
					x--;
					if (x == 0)
					{
						y = k;
						break;
					}
				}
			}
			if (y != -1)
			{
				cnt[belong[y]]--;
				ans -= num[y];
				num[y] = 0;
				vis[y] = 1;
			}
		}
		if (opt == 'Q')
		{
			cout << ans << endl;
		}
	}
	return 0;
}