差分，线段树均摊。调了 2h

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define fi first
#define pb push_back
#define se second
#define int long long
int n, q, a[300010], c[300010];
struct Bit {
	int w[300010];
	void add(int p, int x) {
		for (int i = p; i <= n; i += i & (-i)) w[i] += x;
	}
	int query(int p) {
		int res = 0;
		for (int i = p; i; i -= i & (-i)) res += w[i];
		return res;
	}
} bit;
struct Seg {
	int sm[1200010] /*差分数组 [l, r] 的和*/, tg[1200010] /*原数组区间加标记*/;
	int mx[1200010] /*差分 (l, r] 的 max*/, lft[1200010] /*差分数组 l 的值*/, w[1200010];
	void pu(int u) {
		sm[u] = sm[u << 1] + sm[u << 1 | 1];
		mx[u] = max(mx[u << 1], max(mx[u << 1 | 1], lft[u << 1 | 1]));
		lft[u] = lft[u << 1];
	}
	void build(int u, int l, int r) {
		if (l == r) {
			sm[u] = lft[u] = c[l]; mx[u] = -1e13; return;
		}
		int mid = (l + r) >> 1;
		build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pu(u);
	}
	void mk(int u, int l, int r, int x) {
//		tg[u] += x; sm[u] += x; lft[u] += x; bit.add(l, x), bit.add(r + 1, -x);
	}
	void pd(int u, int l, int r) {
//		int mid = (l + r) >> 1;
//		if (tg[u] != 0) mk(u << 1, l, mid, tg[u]), mk(u << 1 | 1, mid + 1, r, tg[u]); tg[u] = 0;
	}
	void upd(int u, int l, int r, int p, int x) {   // 差分数组 p 值 + x 
		if (l == r) {
			sm[u] += x; lft[u] += x; return;
		}
		pd(u, l, r);
		int mid = (l + r) >> 1;
		if (p <= mid) upd(u << 1, l, mid, p, x);
		else upd(u << 1 | 1, mid + 1, r, p, x); 
		pu(u); 
	}
	int query(int u, int l, int r, int L, int R) {
		if (L > R) return 0;
		if (L <= l && R >= r) return sm[u];
		else if (!(R < l || r < L)) {
			pd(u, l, r);
			int mid = (l + r) >> 1;
			return query(u << 1, l, mid, L, R) + query(u << 1 | 1, mid + 1, r, L, R); 
		} return 0;
	}
	void cao(int u, int l, int r, int L, int R) {   // 原数组 [l, r] 取 popcount，更新差分数组 
		if (R < l || r < L) return;
		if (l != r && mx[u] == 0 && sm[u] - lft[u] == 0) {
			int fw = bit.query(l);
			int a = __builtin_popcount(fw) - fw;
			upd(1, 1, n, l, a); if (r + 1 < n) upd(1, 1, n, r + 1, -a);
//			mk(u, l, r, );	
			bit.add(l, a), bit.add(r + 1, -a);
			return;
//			cout << "Its " << l << " " << r << "\n";return;
		}
		if (l == r) {
			int fl = bit.query(l - 1), fr = bit.query(l), ffr = fr;
			fr = __builtin_popcount(fr); sm[u] = lft[u] = fr - fl; bit.add(l, fr - ffr), bit.add(l + 1, ffr - fr);
		} else {
			pd(u, l, r);
			int mid = (l + r) >> 1;
			cao(u << 1, l, mid, L, R);
			cao(u << 1 | 1, mid + 1, r, L, R); pu(u);
		}
	}
	void dao(int u, int l, int r, int p) {
		if (l == r) {
			lft[u] = sm[u] = bit.query(l) - bit.query(l - 1);
		} else {
			int mid = (l + r) >> 1;
			pd(u, l, r);
			if (p <= mid) dao(u << 1, l, mid, p); else dao(u << 1 | 1, mid + 1, r, p); pu(u);
		}
	}
} tree; 
signed main() {
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i]; c[i] = a[i] - a[i - 1]; bit.add(i, c[i]);
	}
	tree.build(1, 1, n);
	while (q--) {
		char op;
		cin >> op;
		int l, r, x;
		if (op == 'A') {
			cin >> l >> r >> x;
			bit.add(l, x); bit.add(r + 1, -x);
			tree.upd(1, 1, n, l, x);
			if (r + 1 <= n) tree.upd(1, 1, n, r + 1, -x);
		} else if (op == 'P') {
			cin >> l >> r;
			tree.cao(1, 1, n, l, r);
			if (r + 1 <= n) tree.dao(1, 1, n, r + 1); 
		} else {
			cin >> x;
			cout << bit.query(x) << "\n";
		}
//		cout << "Upd: ";
//		for (int i = 1; i <= n; i++) cout << bit.query(i) << " ";
//		cout << "\n";
//		cout << "Cha: ";
//		for (int i = 1; i <= n; i++) cout << tree.query(1, 1, n, i, i) << " ";
//		cout << "\n";
	} 
	return 0;
}