维护一个W*W的矩阵，初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

第一行两个整数,S,W;其中S为矩阵初始值;W为矩阵大小

接下来每行为一下三种输入之一(不包含引号):

"1 x y a"

"2 x1 y1 x2 y2"

"3"

输入1:你需要把(x,y)(第x行第y列)的格子权值增加a

输入2:你需要求出以左上角为(x1,y1),右下角为(x2,y2)的矩阵内所有格子的权值和,并输出

输入3:表示输入结束

对于每个输入2,输出一行,即输入2的答案

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

3
5

保证答案不会超过int范围

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <algorithm>

#include <iostream>

using namespace std;

const int maxn = ;

const int maxm = +;

int s, w, ans[maxm];

struct Node

{

    int op, id, x, y, k, to;

    Node (int op = , int id = , int x = , int y = , int k = , int to = ):

        op(op), id(id), x(x), y(y), k(k), to(to) {}

    bool operator < (const Node &AI) const

    {

        if (x == AI.x && y == AI.y)

            return op < AI.op;

        if (x == AI.x)

            return y < AI.y;

        return x < AI.x;

    }

}q[maxm], temp[maxm];

struct BIT

{

    int c[maxn+];

    int lowbit(int x)

    {

        return x & -x;

    }

    void update(int x, int d)

    {

        while (x <= w)

        {

            c[x] += d;

            x += lowbit(x);

        }

    }

    int query(int x)

    {

        int ret = ;

        while (x > )

        {

            ret += c[x];

            x -= lowbit(x);

        }

        return ret;

    }

}T;

void cdq(int l, int r)

{

    if (l == r)

        return ;

    int mid = (l+r)>>;

    for (int i = l; i <= r; ++i)

    {

        if (q[i].id <= mid && q[i].op == )

            T.update(q[i].y, q[i].k);

        if (q[i].id > mid && q[i].op == )

            ans[q[i].to] += q[i].k*T.query(q[i].y);

    }

    for (int i = l; i <= r; ++i)

        if (q[i].id <= mid && q[i].op == )

            T.update(q[i].y, -q[i].k);

    int t1 = l-, t2 = mid;

    for (int i = l; i <= r; ++i)

        if (q[i].id <= mid)

            temp[++t1] = q[i];

        else

            temp[++t2] = q[i];

    for (int i = l; i <= r; ++i)

        q[i] = temp[i];

    cdq(l, mid), cdq(mid+, r);

}

int main()

{

    scanf("%d %d", &s, &w);

    w += ;

    int oper, cnt = , cnt_2 = ;

    while (~scanf("%d", &oper) && oper != )

    {

        if (oper == )

        {

            int x, y, d;

            scanf("%d %d %d", &x, &y, &d);

            x += , y += ;

            q[++cnt] = Node(, cnt, x, y, d, );

        }

        else

        {

            int x1, y1, x2, y2;

            scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

            x1 += , y1 += , x2 += , y2 += ;

            cnt_2 ++;

            ans[cnt_2] = s*(x2-x1+)*(y2-y1+);

            q[++cnt] = Node(, cnt, x2, y2, , cnt_2);

            q[++cnt] = Node(, cnt, x1-, y2, -, cnt_2);

            q[++cnt] = Node(, cnt, x2, y1-, -, cnt_2);

            q[++cnt] = Node(, cnt, x1-, y1-, , cnt_2);

        }

    }

    sort(q+, q+cnt+);

    cdq(, cnt);

    for (int i = ; i <= cnt_2; ++i)

        printf("%d\n", ans[i]);

    return ;

}