记录

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

int n, m, N;
int SQ;
int arr[600005];

struct sec{
	int l, r, sum, len;
};
sec secs[800];

int Sum;

void init()
{
	int idx;
	SQ = sqrt(n);
	for(int i = 0; i < n; i++){
		idx = i / SQ;
		if(arr[i] != 0x3f3f3f3f3f3f3f3fl){
			secs[idx].sum++;如果有妹子就计数
			Sum += arr[i];
		}
		secs[idx].l = idx * SQ;
		secs[idx].r = i;确定左右端点
	}
}

void add(int pos, int x)// I 操作
{
	int idx = pos / SQ;
 
	if(arr[pos] != 0x3f3f3f3f3f3f3f3fl){
		Sum -= arr[pos]; //如果有妹子减去贡献
	}
	else{
		secs[idx].sum ++;//如果没有就加入总和
	}
	arr[pos] = x;
	Sum += x;//维护答案
}

void dec(int pos, int x)	//C 操作
{
	if(arr[pos] != 0x3f3f3f3f3f3f3f3fl){
		Sum -= x;//如果有妹子
		arr[pos] -= x;
	}
}

void del(int pos) //D 操作
{
	int s = 0;
	int idx = 0;
	s = secs[0].sum;
	while(s < pos && idx <= n / SQ){
		idx++;
		s += secs[idx].sum;
	}//找到所在块
	if(idx > n / SQ){
		return ;
	}
	
	if(s >= pos){
		s -= secs[idx].sum;
		for(int i = secs[idx].l; i <= secs[idx].r; i++){
			if(arr[i] != 0x3f3f3f3f3f3f3f3fl){
				s++;
			}
			if(s == pos){//找到位置
				Sum -= arr[i];
				arr[i] = 0x3f3f3f3f3f3f3f3fl;
				secs[idx].sum--;
			}
		}
	}
}

void Deal()
{
	char temp[2];
	n = 500001;
	memset(arr, 0x3f, sizeof(arr));
	scanf("%lld %lld", &N, &m);
	for(int i = 0; i < N; i++){
		scanf("%lld", arr + i);
	}
	init();
	int x, y;
	for(int i = 1; i <= m; i++){
		scanf("%s", temp);
		switch(temp[0]){
			case 'C':{
				scanf("%lld %lld", &x, &y);
				x--;//以0为下标
				dec(x, y);
				break;
			}
			case 'I':{
				scanf("%lld %lld", &x, &y);
				x--;
				add(x, y);
				break;
			}
			case 'D':{
				scanf("%lld", &x);
				del(x);
				break;
			}
			case 'Q':{
				printf("%lld\n", Sum);
				break;
			}
		}
	}
}

signed main()
{
	Deal();
	return 0;
}

感觉逻辑没错啊