BZOJ 1176 [Balkan2007]Mokia CDQ

Description

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

Input

第一行两个整数,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:表示输入结束

Output

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

Sample Input

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

Sample Output

3
5

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 800005;
struct Query
{
    int x, y, op, val, id, pos;
    bool operator < (const Query &a) const
    {
        return x == a.x ? op < a.op : x < a.x;
    }
} Ask[MAXN], tmp[MAXN];
int n, m, Ans[MAXN];
#define lowbit(_) ((_)&(-_))
struct BIT
{
    int Sum[2000005];
    void add(int x, int c)
    {
        for (int i = x; i <= n; i += lowbit(i))
            Sum[i] += c;
    }
    int Query(int x)
    {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i))
            ans += Sum[i];
        return ans;
    }
}bit;
void add()
{
    int x1, y1, x2, y2;
    scanf ("%d%d%d%d", &x1, &y1, &x2, &y2);
    ++Ans[0];
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y1 - 1, Ask[m].val = 1, Ask[m].op = 1;
    Ask[++m].pos = Ans[0], Ask[m].x = x2    , Ask[m].y = y2    , Ask[m].val = 1, Ask[m].op = 1;
    Ask[++m].pos = Ans[0], Ask[m].x = x1 - 1, Ask[m].y = y2    , Ask[m].val =-1, Ask[m].op = 1;
    Ask[++m].pos = Ans[0], Ask[m].x = x2    , Ask[m].y = y1 - 1, Ask[m].val =-1, Ask[m].op = 1;
}
void CDQ(int l, int r)
{
    if (l == r)
        return;
    int mid = l + r >> 1, l1 = l, l2 = mid + 1;
    for (int i = l; i <= r; i++)
    {
        if (Ask[i].id <= mid && !Ask[i].op)
            bit.add(Ask[i].y, Ask[i].val);
        if (Ask[i].id > mid && Ask[i].op)
            Ans[Ask[i].pos] += Ask[i].val * bit.Query(Ask[i].y);
    }
    for (int i = l; i <= r; i++)
        if (Ask[i].id <= mid && !Ask[i].op)
            bit.add(Ask[i].y, -Ask[i].val);
    for (int i = l; i <= r; i++)
    {
        if (Ask[i].id <= mid)
            tmp[l1++] = Ask[i];
        else tmp[l2++] = Ask[i];
    }
    for (int i = l; i <= r; i++)
        Ask[i] = tmp[i];
    CDQ(l, mid);
    CDQ(mid + 1, r);
    return;
}
int main()
{
    freopen("mokia.in", "r", stdin);
    freopen("mokia.out", "w", stdout);
    int op;
    scanf ("%d%d", &op, &n);
    while (1)
    {
        scanf ("%d", &op);
        if (op == 1)
        {
            m++;
            scanf ("%d%d%d", &Ask[m].x, &Ask[m].y, &Ask[m].val);
        }
        else if (op == 2)
            add();
        else break;
    }
    for (int i = 1; i <= m; i++)
        Ask[i].id = i;
    sort(Ask + 1, Ask + m + 1);
    CDQ(1 ,m);
    for (int i = 1; i <= Ans[0]; i++)
        printf ("%d\n", Ans[i]);
}