虽然两个做法都是 $O(nlog^2n)$ ，看到很多大佬使用树状数组随便3s多过了，而蒟蒻上了CDQ套CDQ还得改一下写法卡常，仍然有10s以上。 是因为第一层CDQ的排序和第二层CDQ的复杂逻辑吗？

愿意康的话这里贴了代码，大量指针警告:(

#include <cstdio>
#include <cctype>
#include <algorithm>
#define rep(i, l, r) for (int i = l, i##e = r; i <= i##e; ++i)
using namespace std;
typedef long long ll;

const int MAXN = 1e6;

struct vec3
{
    int t, x, y, k, id;
    char mark;
    bool operator<(const vec3 &a) const
    {
        if (t != a.t) return t < a.t;
        if (x != a.x) return x < a.x;
        return y < a.y;
    }
} a[MAXN], *top = a;
auto cmpx = [](const vec3 &a, const vec3 &b) { return a.x < b.x; };

int ans[MAXN];

void cdq2(vec3 *begin, vec3 *end)
{
    static vec3 tmp[MAXN];
    if (begin + 1 == end) return;
    vec3 *mid = begin + (end - begin) / 2;
    cdq2(begin, mid), cdq2(mid, end);
    vec3 *l = begin, *r = mid, *p = tmp;
    ll sumk = 0, sumxyk = 0, sumxk = 0, sumyk = 0;
    while (r < end)
    {
        while (l < mid && l->y <= r->y)
        {
            if (l->mark == 'L')
            {
                sumk += l->k;
                sumxyk += 1ll * l->x * l->y * l->k;
                sumxk += 1ll * l->x * l->k;
                sumyk += 1ll * l->y * l->k;
            }
            *p++ = *l++;
        }
        if (r->mark == 'R')
        {
            int x0 = r->x, y0 = r->y;
            ans[r->id] +=
                + (1ll * x0 * y0 + x0 + y0 + 1) * sumk 
                - (y0 + 1) * sumxk - (x0 + 1) * sumyk 
                + sumxyk;
        }
        *p++ = *r++;
    }
    while (l < mid) *p++ = *l++;
    copy(tmp, p, begin);
}

void cdq(vec3 *begin, vec3 *end)
{
    if (begin + 1 == end) return;
    vec3 *mid = begin + (end - begin) / 2;
    int edge = mid->t;
    cdq(begin, mid), cdq(mid, end);
    for (vec3 *p = begin; p < end; ++p)
        p->mark = p->t < edge ? 'L' : 'R';
    stable_sort(begin, end, cmpx);
    cdq2(begin, end);
}

int n, m;

int time, quecnt;
void query(int x1, int y1, int x2, int y2)
{
    ++quecnt;
    *top++ = vec3{++time, x2, y2, 0, 4 * quecnt - 3};
    *top++ = vec3{++time, x1 - 1, y2, 0, 4 * quecnt - 2};
    *top++ = vec3{++time, x2, y1 - 1, 0, 4 * quecnt - 1};
    *top++ = vec3{++time, x1 - 1, y1 - 1, 0, 4 * quecnt};
}

void mdfy(int x1, int y1, int x2, int y2, int k)
{
    *top++ = vec3{++time, x1, y1, k, 0};
    *top++ = vec3{++time, x2 + 1, y1, -k, 0};
    *top++ = vec3{++time, x1, y2 + 1, -k, 0};
    *top++ = vec3{++time, x2 + 1, y2 + 1, k, 0};
}

void answer(void)
{
    rep(i, 1, quecnt)
    {
        long long res = 0;
        res += ans[4 * i - 3];
        res -= ans[4 * i - 2];
        res -= ans[4 * i - 1];
        res += ans[4 * i];
        printf("%lld\n", res);
    }
}

int main(void)
{
    scanf("X %d %d", &n, &m);
    char op[10];
    while (scanf("%s", op) != EOF)
    {
        int a, b, c, d, k;
        if (op[0] == 'L')
            scanf("%d%d%d%d%d", &a, &b, &c, &d, &k), mdfy(a, b, c, d, k);
        else
            scanf("%d%d%d%d", &a, &b, &c, &d), query(a, b, c, d);
    }
    return cdq(a, top), answer(), 0;
}