HDU - 1166 CDQ分治

题意：

思路：

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;}