老C的任务问题

解题思路

有若干个二维的点，对于每个询问，找出询问的矩形中所有点的权值和。

要想快速求出一个一个矩阵内的权值和，可以用二维前缀和来求。因此我们现在其实只需要快速求出来某一个点的二维前缀和，就能求出所有矩阵的区间和。但是本题的数据范围让我们无法预处理出所有的二维前缀和，因此需要考虑其他做法。

可以发现，一个数的二维前缀和其实就是他的左下方所有点的权值和，因此我们就是要快速求出每个点左下方所有点的权值和，假设当前点是 $x_i,y_i$，则在它左下方的点 $(x_j,y_j)$ 一定满足 $x_j \leq x_i, y_j \leq y_i$，因此我们就是要快速所有满足要求的元素的权值和，然后题目中查询的点和被查询的点还需要区分开，因此我们可以再标记一个信息，$z_i$，查询的点 $z_i=1$，被查询的点 $z_i=0$，那么问题就变成对于每个点 $(x_i,y_i,z_i)$ 求出所有满足 $x_j \leq x_i,y_j \leq y_i,z_j < z_i$ 的所有点的权值之和

可以发现这就是一个三维偏序问题，因此可以用 CDQ 分治来做，但是这里还有一个小的区别，就是本题的 $z_i$ 只有 $0,1$ 两种取值，而我们每次其实就是对于 $z_i=1$ 的点去求他左下方所有 $z_i=0$ 的点的数量，因此第三维其实就不需要用树状数组去维护了，我们可以直接用一个变量 $sum$ 来维护当前 $1$ 的个数，就能直接计算得到 $0$ 的数量。

由于不需要用到树状数组，本题的 CDQ 分治的时间复杂度就会降为 $O(nlogn)$

我们这里其实是用的一个离线的做法，将所有的点全部读入进来，然后计算完答案之后，再枚举所有的矩形通过前缀和将答案计算出来。

然后这里由于我们计算的时候是求第三维严格小于的点的数量，因此不会考虑相同的点，所以也不需要进行判重。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
struct Data
{
    //x, y, z 表示当前点的坐标
    //p 表示当前点的权值
    //id 表示当前点是不是查询点，如果是查询点还需要记录是哪个查询
    //sign 表示当前点的前缀和需要加上还是减去
    int x, y, z, p, id, sign;
    LL sum; //sum 表示满足要求的点的权值和
    bool operator< (const Data &t) const
    {
        if(x != t.x) return x < t.x;
        if(y != t.y) return y < t.y;
        return z < t.z;
    }
}q[N], w[N]; //存储所有三维的点，w 是临时数组
LL res[N]; //记录答案

void merge_sort(int l, int r)
{
    if(l >= r) return;

    int mid = l + r >> 1;
    merge_sort(l, mid), merge_sort(mid + 1, r); //递归左、右区间

    int i = l, j = mid + 1, k = 0;
    LL sum = 0; //记录当前满足条件的所有点的权值和
    while(i <= mid && j <= r)
        if(q[i].y <= q[j].y) sum += !q[i].z * q[i].p, w[k++] = q[i++];
        else q[j].sum += sum, w[k++] = q[j++];
    while(i <= mid) sum += !q[i].z * q[i].p, w[k++] = q[i++];
    while(j <= r) q[j].sum += sum, w[k++] = q[j++];
    for(int i = l, j = 0; j < k; i++, j++) q[i] = w[j];
}

int main()
{
    scanf("%d%d", &n, &m);

    for(int i = 0; i < n; i++)
    {
        int x, y, p;
        scanf("%d%d%d", &x, &y, &p);
        q[i] = {x, y, 0, p};
    }
    int k = n;
    for(int i = 1; i <= m; i++)
    {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        //S = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
        q[k++] = {x2, y2, 1, 0, i, 1};
        q[k++] = {x1 - 1, y2, 1, 0, i, -1};
        q[k++] = {x2, y1 - 1, 1, 0, i, -1};
        q[k++] = {x1 - 1, y1 - 1, 1, 0, i, 1};
    }

    sort(q, q + k); //将所有点按三关键字排序

    merge_sort(0, k - 1); //CDQ 分治

    //处理答案
    for(int i = 0; i < k; i++)
        if(q[i].z)
            res[q[i].id] += q[i].sum * q[i].sign;

    for(int i = 1; i <= m; i++) printf("%lld\n", res[i]); //输出答案

    return 0;
}