題意：

思路：

HDU-1166這題，我們把他轉化成一個二維偏序問題，每個操作用一個有序對(a,b)表示，其中a表示操作到來的時間，b表示操作的位置，時間是默認有序的，所以我們在合并子問題的過程中，就按照b從小到大的順序合并。

關鍵是如何表示查詢和修改，用結構體Query統一標識查詢和修改，其中包含三個元素，type,pos,val。其中查詢[L,R]的和看作兩個部分組成查詢sum[R]和sum[L-1]。

1.type為1時表示修改操作，pos是修改的位置，val是添加的值。

2.type為2時表示針對左端點的前綴和查詢，pos是左端點位置，val是該查詢的編號，為了方便記錄答案。

3.type為3時表示針對右端點的前綴和查詢，pos是右端點位置，val是查詢編號。

代碼中的ans數組儲存對于詢問的答案。按照cdq分治的思路，因為各個操作的時間順序已經默認，所以就直接將所有操作放入que數組中進行分治，為了方便討論所有區間都是左閉右開，對于下標為[L,R)的區間，先分成[L,M)和[M,R)遞歸處理，然后歸并，要考慮左部分的修改，對于右部分的查詢造成的影響，對于本題來說就是左部分修改操作后的變化量和，對于查詢操作，要查詢的是sum[R]-sum[L]，這里L位置之前的修改操作的變化量和add都會對其有影響，如果查詢的pos是左端點，ans[id]要減去add，若是右端點，ans[id]要加上add。

具體細節需要到代碼中領悟。

代碼：

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int MAXN = 50005;const int MAXM = 40005;const int MAXQ = MAXM * 2 + MAXN;struct Query {    int type, pos, val;    bool Operator < (const Query &rhs) const {        return pos == rhs.pos ? type < rhs.type : pos < rhs.pos;  // 同一位置，修改操作要先于查詢操作    }}que[MAXQ], tmp[MAXQ];int ans[MAXQ];int qnum, anum;     // qnum表示所有有序對的個數，anum表示詢問操作的個數void cdq(int l, int r) {    if (l + 1 >= r) return;    int m = (l + r) >> 1;    cdq(l, m); cdq(m, r);    int p = l, q = m, cnt = 0, sum = 0;    while (p < m && q < r) {         // 類似歸并排序的模式，換成了處理有序對        if (que[p] < que[q]) {            if (que[p].type == 1) sum += que[p].val;   // 左半部分先發生的修改操作，保存變化量的和sum            tmp[cnt++] = que[p++];        }        else {            if (que[q].type == 2) ans[que[q].val] -= sum;       // 左端點查詢減去sum            else if (que[q].type == 3) ans[que[q].val] += sum;      // 右端點查詢加上sum            tmp[cnt++] = que[q++];        }    }    while (p < m) tmp[cnt++] = que[p++];    while (q < r) {        if (que[q].type == 2) ans[que[q].val] -= sum;        else if (que[q].type == 3) ans[que[q].val] += sum;        tmp[cnt++] = que[q++];    }    for (int i = 0; i < cnt; i++)       // 利用臨時數組更新操作數組que        que[i + l] = tmp[i];}char op[10];int main() {    //freopen("in.txt", "r", stdin);    int T, cs = 0;    scanf("%d", &T);    while (T--) {        int n, x;        scanf("%d", &n);        qnum = anum = 0;        for (int i = 1; i <= n; i++, qnum++) {            scanf("%d", &x);            que[qnum] = (Query) {1, i, x};        }        while (true) {            scanf("%s", op);            if (op[0] == 'E') break;            if (op[0] == 'Q') {                int l, r;                scanf("%d%d", &l, &r);                que[qnum++] = (Query) {2, l - 1, anum};                que[qnum++] = (Query) {3, r, anum++};            }            else {                int pos, add;                scanf("%d%d", &pos, &add);                add *= (op[0] == 'A' ? 1 : -1);                que[qnum++] = (Query) {1, pos, add};            }        }        memset(ans, 0, sizeof(ans));      // 記得ans清零        cdq(0, qnum);        PRintf("Case %d:/n", ++cs);        for (int i = 0; i < anum; i++)            printf("%d/n", ans[i]);    }    return 0;}