分块 30 pts 求调

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e5 + 5, T = 805, len = 5e5;
int n, m;
int a[N];
bool c[N];
int block, tot;
int l[T], r[T], belong[N], cnt[T], sum[T];

void Build()
{
	block = sqrt(len);
	tot = (len + block - 1) / block;
	for (int i = 1; i <= tot; ++i)
	{
		l[i] = (i - 1) * block + 1;
		r[i] = i * block;
	}
	r[tot] = len;
	for (int i = 1; i <= len; ++i)
		belong[i] = (i - 1) / block + 1;
	for (int i = 1; i <= tot; ++i)
		for (int j = l[i]; j <= r[i]; ++j)
			sum[i] += a[j], cnt[i] += c[j];
}

void Change(int x, int k)
{
	if (!c[x])
		return;
	sum[belong[x]] -= k;
	a[x] -= k;
}

void Insert(int x, int k)
{
	if (c[x])
	{
		sum[belong[x]] += k - a[x];
		a[x] = k;
	}
	else
	{
		c[x] = 1, a[x] = k;
		sum[belong[x]] += a[x];
		++cnt[belong[x]];
	}
}

void Delete(int x)
{
	int p = 1;
	while (x - cnt[p] > 0 && p <= tot)
		++p, x -= cnt[p];
	if (p == tot)
		return;
	for (int i = l[p]; i <= r[p]; ++i)
	{
		if (c[i])
			--x;
		if (!x)
		{
			sum[p] -= a[i], --cnt[p];
			c[i] = 0, a[i] = 0;
			return;
		}
	}
}

int Query()
{
	int res = 0;
	for (int i = 1; i <= tot; ++i)
		res += sum[i];
	return res;
}

signed main()
{
	scanf("%lld%lld", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%lld", a + i), c[i] = 1;
	Build();
	while (m--)
	{
		char op[5];
		int x, k;
		scanf(" %s", op);
		if (*op == 'C')
		{
			scanf("%lld%lld", &x, &k);
			Change(x, k);
		}
		else if (*op == 'I')
		{
			scanf("%lld%lld", &x, &k);
			Insert(x, k);
		}
		else if (*op == 'D')
		{
			scanf("%lld", &x);
			Delete(x);
		}
		else
			printf("%lld\n", Query());
	}
	return 0;
}