传送门

一般CDQ分治。

如果用二维BIT在线做的话，空间是不能承受的。所以考虑CDQ离线。

如果没有加数操作，只有询问，那么按照x排序，在y方向维护树状数组，就可以算出每个询问的答案。

现在有了加数操作，相当于时间变成了第三位。于是先按第三维排序，进行CDQ分治。每次分治之后把前一半的修改对后一半询问的影响看成一个离线询问。

然后玄学的地方出现了

把y坐标进行离散化。TLE

优化常数一，对每个y坐标改为它离散化后的相对大小，减小查询常数。TLE（甚至一组都过不了

优化常数二，把坐标离散化后再离线，对于每个下标 i 的坐标y，都存在idx[]数组里访问。TLE

优化常数三，把unorder_map改为了int数组，查询y坐标的时候直接访问数组，TLE

以上操作二和操作三是分开的，也就是说，两个理论查询复杂度O(1)的操作都是TLE

优化常数四，把操作二和操作三合并，理论上还是O(1)的而且常数还稍大了一点。AC……

#include<bits/stdc++.h>
using namespace std;
//unordered_map<int,int> ump;
const int maxn = 1e6 + 233;
struct Node{
    int x, y, t, v;
}q[maxn], b[maxn];
int ans[maxn], c[maxn], tot = 0, idx[maxn];
int ump[maxn * 2];
inline void add(int x, int v)
{
    for(; x <= tot; x += x & -x) c[x] += v;
}
inline int ask(int x)
{
    int res = 0;
    for(; x; x -= x & -x) res += c[x];
    return res;
}
bool cmp(const Node &a, const Node &b)
{
    if(a.x == b.x && a.y == b.y) return a.t < b.t;
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x; 
}
inline int get(int x)
{
    //return ump[b[x].y];
    return idx[b[x].t];
}
void gao(int l, int r)
{
    for(int i = l; i <= r; i++)
    {
        if(q[b[i].t].t == 1) add(get(i), b[i].v);
        else ans[b[i].t] += ask(get(i));
    }
    for(int i = l; i <= r; i++)
    {
        if(q[b[i].t].t == 1) for(register int x = get(i); x <= tot; x += x & -x) c[x] -= b[i].v;
    }
}
void cdq(int l, int r)
{
    int mid = (l + r) >> 1;
    if(l < mid) cdq(l, mid);
    if(mid + 1 < r) cdq(mid + 1, r);
    int n = 0;
    for(int i = l; i <= r; i++)
    {
        if(i <= mid && q[i].t == 1 || i > mid && q[i].t == 2) b[++n] = {q[i].x, q[i].y, i, q[i].v}; 
    }
    stable_sort(b + 1, b + 1 + n, cmp);
    gao(1, n);
}
set<int> st;
int main()
{
    int S, W;
    scanf("%d%d", &S, &W);
    int op = 0, qs = 0;

    while(1)
    {
        scanf("%d", &op);
        if(op == 3) break;
        if(op == 2)
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            q[++qs] = {x2, y2, 2, 1};  st.insert(y2);
            q[++qs] = {x1 - 1, y1 - 1, 2, 1};  st.insert(y1 - 1);
            q[++qs] = {x1 - 1, y2, 2, -1}; 
            q[++qs] = {x2, y1 - 1, 2, -1};
            ans[qs] = S * (x2 - x1 + 1) * (y2 - y1 + 1);
        }
        else 
        {
            int x, y, a;
            scanf("%d%d%d", &x, &y, &a);
            q[++qs] = {x, y, 1, a};  st.insert(y);
        }
    }

    for(auto it = st.begin(); it != st.end(); it++)
    {
        ump[*it] = ++tot;
    }
    for(int i = 1; i <= qs; i++) idx[i] = ump[q[i].y];
    // cerr << qs << endl;
    cdq(1, qs);
    // for(int i = 0; i <= 4; i++) cerr << ump[i] << " "; puts("");
    for(int i = 1; i <= qs; i++)
    {
        if(q[i].t == 2)
        {
            int val = 0;
            for(register int j = 0; j < 4; j++)
            {
                int tmp = q[i + j].v * ans[i + j]; 
                // cerr << tmp << "?" << endl;
                val += tmp;
            }
            printf("%d\n", val);
            i += 3;
        }
    }
}

注意在ump是数组的情况下

inline int get(int x)
{
    //return ump[b[x].y];
    return idx[b[x].t];
}

两行代码的复杂度应该是一样的。然而一个能A一个不能…….

本弱决定暂时称其为卡常离散化，如果有大佬知道是什么情况请指正……….