bzoj1176 [Balkan2007]Mokia

1176: [Balkan2007]Mokia

Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 2899 Solved: 1296
[Submit][Status][Discuss]

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

HINT

保证答案不会超过int范围

分析：非常好的一道题.因为只有修改和查询操作，并且修改操作互相独立且题目允许离线，所以可以用cdq分治来做.那么题目就被简化成了:先让一些点的权值+a,接着给出一些询问，求子矩阵的和.

问题简化后还是难以处理，因为矩阵太大了，存不下，最多只能存一维.子矩阵求和可以想到用二维前缀和来处理，那么可以将一个矩阵拆成4个小矩阵，只需要计算每个点对这些小矩阵的贡献就好了.点i对矩阵j有贡献当且仅当,i操作在j操作前，并且i的xy坐标都≤j的xy坐标，那么这就成了一个三维偏序问题.一维用一种方法：对于操作的时间，用cdq分治;对于x坐标，排序;对于y坐标，树状数组统计维护.处理完了后将操作时间≤mid的放在一组，＞mid的放在另一组，分治下去.也就是说要先求大区间的答案，再来求小区间的答案.当然，并不是所有的题都是要先求大区间再来求小区间，这要根据先后顺序的影响.

注意：排序一定要根据三个量排彻底!一开始只排了xy坐标，WA了两个点.

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

using namespace std;

typedef long long ll;
ll s,n,tot,ans[200010],cnt,c[2000010];
int op;

struct node
{
    ll x,y,id,v,flag,ansid;
} e[200010],p[200010];

bool cmp(node a,node b)
{
    if (a.x == b.x && a.y == b.y)
        return a.id < b.id;
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

void add(ll x,ll v)
{
    while (x <= n)
    {
        c[x] += v;
        x += x & (-x);
    }
}

ll query(ll x)
{
    ll res = 0;
    while (x)
    {
        res += c[x];
        x -= x & (-x);
    }
    return res;
}

void solve(int l,int r)
{
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    for (int i = l; i <= r; i++)
    {
        if (e[i].id <= mid && e[i].flag == 1)
            add(e[i].y,e[i].v);
        else if (e[i].id > mid && e[i].flag == -1)
            ans[e[i].ansid] += e[i].v * query(e[i].y);
    }
    for (int i = l; i <= r; i++)
        if (e[i].id <= mid && e[i].flag == 1)
            add(e[i].y,-e[i].v);
    int L = l,R = mid + 1;
    for (int i = l; i <= r; i++)
    {
        if (e[i].id <= mid)
            p[L++] = e[i];
        else
            p[R++] = e[i];
    }
    for (int i = l; i <= r; i++)
        e[i] = p[i];
    solve(l,mid),solve(mid + 1,r);
}

int main()
{
    scanf("%lld%lld",&s,&n);
    while (scanf("%d",&op) && op != 3)
    {
        if (op == 1)
        {
            tot++;
            scanf("%lld%lld%lld",&e[tot].x,&e[tot].y,&e[tot].v);
            e[tot].id = tot;
            e[tot].flag = 1;
        }
        else
        {
            ll x3,x4,y3,y4;
            scanf("%lld%lld%lld%lld",&x3,&y3,&x4,&y4);
            ans[++cnt] = (x4 - x3 + 1) * (y4 - y3 + 1) * s;

            e[++tot].x = x3 - 1;
            e[tot].y = y3 - 1;
            e[tot].id = tot;
            e[tot].v = 1;
            e[tot].flag = -1;
            e[tot].ansid = cnt;

            e[++tot].x = x4;
            e[tot].y = y4;
            e[tot].id = tot;
            e[tot].v = 1;
            e[tot].flag = -1;
            e[tot].ansid = cnt;

            e[++tot].x = x3 - 1;
            e[tot].y = y4;
            e[tot].id = tot;
            e[tot].v = -1;
            e[tot].flag = -1;
            e[tot].ansid = cnt;

            e[++tot].x = x4;
            e[tot].y = y3 - 1;
            e[tot].id = tot;
            e[tot].v = -1;
            e[tot].flag = -1;
            e[tot].ansid = cnt;
        }
    }
    sort(e + 1,e + 1 + tot,cmp);
    solve(1,tot);
    for (int i = 1; i <= cnt; i++)
        printf("%lld
",ans[i]);

    return 0;
}