BZOJ 1176 [Balkan2007]Mokia

题目大意

给你一个$W \times W$的矩阵，初始值均为$S$，每次操作为：

1. 增加某个格子的权值。
2. 询问子矩阵总权值。

这题首先没啥思路……想到使用前缀和优化，之后问题就变成了求一个左下角为$(0,0)$的矩阵中的点的权值和。而且因为是在线处理所有还有时间一维。所以就想到使用CDQ分治进行优化。

CDQ分治用于解决以下问题：在一个三维空间中，比一个点的X,Y,Z坐标都要小的点的总权值是多少？

首先将所有点按照X坐标进行一次排序。此时确保了所有的$i \lt j$都有$x_i \lt x_j$.之后进行分治。

对于分治的每一层，我们对[l,mid]和[mid+1]分别按照Y坐标排序。此时因为之前的操作就可以保证左面的X都小于右面的X，而分别排序之后左右区间的端点都是Y坐标最大/最小的。

之后根据分治来回取出这些点。每取出一个右区间的点都保证我已经取出的左区间的点都比这个点的X和Y要小。此时用树状数组维护Z就可以了。

注：这题初始值S不要读入……初始值全是0……数据错了但是也没啥办法= =

#include <cstdio>
#include <algorithm>
using namespace std;
int n,mode,inx,iny,ina,inb,f[2000010],tot;
struct query{int x,y,val,id,md;} q[1000010],b[1000010];
bool cmp(query tx,query ty) {return tx.id<ty.id;}
int query(int tx)
{
    int ret=0;
    for(;tx;tx-=tx&-tx) ret+=f[tx];
    return ret;
}
void add(int tx,int ty) {for(;tx<=n;tx+=tx&-tx) f[tx]+=ty;}
void cdq(int l,int r)
{
    if(l>=r) return;
    int mid=(l+r)>>1,p1=l,p2=mid+1;
    cdq(l,mid),cdq(mid+1,r);
    for(int i=l;i<=r;++i)
    {
        if(p1==mid+1||(p2!=r+1&&q[p1].x>q[p2].x))
        {
            if(q[p2].md) q[p2].val+=query(q[p2].y);
            b[i]=q[p2],p2++;
        }
        else
        {
            if(!q[p1].md) add(q[p1].y,q[p1].val);
            b[i]=q[p1],p1++;
        }
    }
    for(int i=l;i<=mid;++i) if(!q[i].md) add(q[i].y,-q[i].val);
    for(int i=l;i<=r;++i) q[i]=b[i];
    return;
}
int main()
{
    scanf("%*d%d",&n);
    while(true)
    {
        scanf("%d",&mode);
        if(mode==3) break;
        if(mode==1)
        {
            scanf("%d%d%d",&inx,&iny,&ina);
            q[++tot].x=inx,q[tot].y=iny,q[tot].val=ina,q[tot].id=tot;
        }
        if(mode==2)
        {
            scanf("%d%d%d%d",&inx,&iny,&ina,&inb);
            q[++tot].x=inx-1,q[tot].y=iny-1,q[tot].md=1,q[tot].id=tot;
            q[++tot].x=inx-1,q[tot].y=inb,q[tot].md=1,q[tot].id=tot;
            q[++tot].x=ina,q[tot].y=iny-1,q[tot].md=1,q[tot].id=tot;
            q[++tot].x=ina,q[tot].y=inb,q[tot].md=1,q[tot].id=tot;
        }
    }
    cdq(1,tot);
    sort(q+1,q+tot+1,cmp);
    for(int i=1;i<=tot;++i)
        if(q[i].md) printf("%d\n",q[i+3].val-q[i+1].val-q[i+2].val+q[i].val),i+=3;
    return 0;
}