[bzoj] 1176 Mokia || CDQ分治

原题

给出W×W的矩阵（S没有用，题目有误），给出无限次操作，每次操作的含义为：

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

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

输入3:表示输入结束

因为修改之间相互独立，所以可以用CDQ。

三个维度分别为时间，x轴，y轴。

简单的三维偏序即可。

#include<cstdio>

#include<algorithm>

#define N 200010

using namespace std;

struct hhh

{

    int x,y,w,pos,id,op;

    bool operator < (const hhh &b) const

	{

	    if (x==b.x && y==b.y) return op<b.op;

	    if (x==b.x) return y<b.y;

	    return x<b.x;

	}

}q[N],tmp[N];

int s,w,n,ans[N],m,op,f[10*N];

int read()

{

    int ans=0,fu=1;

    char j=getchar();

    for (;j<'0' || j>'9';j=getchar()) if (j=='-') fu=-1;

    for (;j>='0' && j<='9';j=getchar()) ans*=10,ans+=j-'0';

    return ans*fu;

}

void addquery()

{

    int lx=read(),ly=read(),rx=read(),ry=read();

    int pos=++ans[0];

    q[++m].pos=pos;q[m].id=m;q[m].x=lx-1;q[m].y=ly-1;q[m].w=1;q[m].op=1;

    q[++m].pos=pos;q[m].id=m;q[m].x=rx;q[m].y=ry;q[m].w=1;q[m].op=1;

    q[++m].pos=pos;q[m].id=m;q[m].x=lx-1;q[m].y=ry;q[m].w=-1;q[m].op=1;

    q[++m].pos=pos;q[m].id=m;q[m].x=rx;q[m].y=ly-1;q[m].w=-1;q[m].op=1;

}

void add(int x,int y)

{

    while (x<=w)

    {

	f[x]+=y;

	x+=x&-x;

    }

}

int query(int x)

{

    int ans=0;

    while (x)

    {

	ans+=f[x];

	x-=x&-x;

    }

    return ans;

}

void CDQ(int l,int r)

{

    if (l==r) return ;

    int mid=(l+r)>>1,i=l,j=mid+1;

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

    {

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

	    add(q[k].y,q[k].w);

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

	    ans[q[k].pos]+=q[k].w*query(q[k].y);

    }

    for (int k=l;k<=r;k++)//清空树状数组

	if (q[k].id<=mid && !q[k].op) add(q[k].y,-q[k].w);

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

	if (q[k].id<=mid) tmp[i++]=q[k];

	else tmp[j++]=q[k];

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

	q[k]=tmp[k];

    CDQ(l,mid);

    CDQ(mid+1,r);

}

int main()

{

    s=read();

    w=read();

    while (1)

    {

	op=read();

	if (op==1)

	{

	    q[++m].x=read();

	    q[m].y=read();

	    q[m].w=read();

	    q[m].id=m;

	}

	else if (op==2)

	    addquery();

	else break;

    }

    sort(q+1,q+m+1);

    CDQ(1,m);

    for (int i=1;i<=ans[0];i++)

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

    return 0;

}

巴特西

[bzoj] 1176 Mokia || CDQ分治

原题

最新文章

热门文章