//分块方法
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
#define int long long

int n, k, a[500005], b[500005], id[500005], s[500005], len;
bool g[500005]; //判断当前城市有没有妹子（有的时候这个城市的妹子颜值为零）

void add(int l, int r, long long x) { //在l和r之间加上x
  int sid = id[l], eid = id[r];
  if (sid == eid) {
    for (int i = l; i <= r; i++) a[i] += x, s[sid] += x;
    return;
  }
  for (int i = l; id[i] == sid; i++) a[i] += x, s[sid] += x;
  for (int i = sid + 1; i < eid; i++) b[i] += x, s[i] += len * x;
  for (int i = r; id[i] == eid; i--) a[i] += x, s[eid] += x;
}

long long query(int l, int r) { //查询l到r的总和
  int sid = id[l], eid = id[r];
  long long ans = 0;
  if (sid == eid) {
    for (int i = l; i <= r; i++) ans = ans + a[i] + b[sid];
    return ans;
  }
  for (int i = l; id[i] == sid; i++) ans = ans + a[i] + b[sid];
  for (int i = sid + 1; i < eid; i++) ans = ans + s[i];
  for (int i = r; id[i] == eid; i--) ans = ans + a[i] + b[eid];
  return ans;
}

signed main() {
  cin >> n >> k;
  len = sqrt(500005);
  char c;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    id[a[i]] = (i - 1) / len + 1;
    s[id[i]] += a[i];
    g[i] = true;//标记有妹子
  }//分块
  int x, y;
  int num;
  while (k--) {
    cin >> c;
    switch (c) {
    case 'C':
      cin >> x >> y;
      add(x, x, -y);
      break;
    case 'I':
      cin >> x >> y;
      g[x] = true;//标记有了妹子
      add(x, x, -query(x, x));//减去x~x（即第x）个城市的妹子的颜值
      add(x, x, y); //加上y的颜值
      break;
    case 'D':
      cin >> x;
      num = 0;
      for (int i = 1; ; i++) {
	if (g[i]) {
	  num++;
	}
	if (num == x) {
	  num = i;
	  break;
	}
      }
      add(num, num, -query(num, num));//减去x~x（即第x）个城市的妹子的颜值，即清零
      g[num] = false;//标记没有妹子
      break;
    case 'Q':
      cout << query(1, 500005) << endl;
      break;
    }
  }
  return 0;
}

评测记录