首页 > 代码库 > 【BZOJ-1176&2683】Mokia&简单题 CDQ分治

【BZOJ-1176&2683】Mokia&简单题 CDQ分治

2024-08-13 00:27:58   218人阅读

1176: [Balkan2007]Mokia

Time Limit: 30 Sec  Memory Limit: 162 MB
Submit: 1854  Solved: 821
[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范围

Source

2683: 简单题

Time Limit: 50 Sec  Memory Limit: 128 MB
Submit: 821  Solved: 339
[Submit][Status][Discuss]

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令

参数限制

内容

1 x y A

1<=x,y<=N，A是正整数

将格子x,y里的数字加上A

2 x1 y1 x2 y2

1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和

3

无

终止程序

Input

输入文件第一行一个正整数N。
接下来每行一个操作。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

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

1<=N<=500000,操作数不超过200000个，内存限制20M。
对于100%的数据，操作1中的A不超过2000。

Source

 

Solution

不能直接硬做，所以利用CDQ分治，大致的过程是：

首先把一个询问操作，拆成4个..++--；

然后我们所有操作进行排序，按x维排序；

然后对y维建立树状数组，这里我们可以发现，如果按x从小到大的处理的话，一次询问，相当于是对y维取前缀和；

然后CDQ(l,r)，枚举这些操作，如果修改操作序号＜=mid，那么就修改；如果查询操作序号>mid那么就计算答案。这样按x进行的排序和输入顺序就不矛盾了，可以得到正确答案

然后还要还原，然后递归分治即可

Code

BZOJ2683：

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;inline int read(){    int x=0; char ch=getchar();    while (ch<‘0‘ || ch>‘9‘) {ch=getchar();}    while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}    return x;}#define MAXQ 200010#define MAXN 500010int S,W,ans[MAXQ];namespace BIT{    int tree[MAXN];    inline int lowbit(int x) {return x&-x;}    inline void Change(int pos,int D) {for (int i=pos; i<=W; i+=lowbit(i)) tree[i]+=D;}    inline int Query(int pos) {int re=0; for (int i=pos; i; i-=lowbit(i)) re+=tree[i]; return re;}}using namespace BIT;struct AskNode{    int id,x,y,opt,del,ID;    bool operator < (const AskNode & A) const        {            return (x==A.x && y==A.y)? opt<A.opt: ((x==A.x)? y<A.y:x<A.x);        }}q[MAXQ<<2],tmp[MAXQ<<2];void CDQ(int l,int r){    if (l==r) return;    int mid=(l+r)>>1,z1=l,z2=mid+1;    for (int i=l; i<=r; i++)        {             if (q[i].opt==1 && q[i].id<=mid) BIT::Change(q[i].y,q[i].del);            if (q[i].opt==2 && q[i].id>mid) ans[q[i].ID]+=BIT::Query(q[i].y)*q[i].del;        }    for (int i=l; i<=r; i++) if (q[i].opt==1 && q[i].id<=mid) BIT::Change(q[i].y,-q[i].del);    for (int i=l; i<=r; i++) if (q[i].id<=mid) tmp[z1++]=q[i]; else tmp[z2++]=q[i];    for (int i=l; i<=r; i++) q[i]=tmp[i];    CDQ(l,mid); CDQ(mid+1,r);}int z,t;void PreWork(int x1,int y1,int x2,int y2){    z++;    t++; q[t].id=t; q[t].ID=z; q[t].x=x1-1; q[t].y=y1-1; q[t].del=1; q[t].opt=2;    t++; q[t].id=t; q[t].ID=z; q[t].x=x2; q[t].y=y2; q[t].del=1; q[t].opt=2;    t++; q[t].id=t; q[t].ID=z; q[t].x=x1-1; q[t].y=y2; q[t].del=-1; q[t].opt=2;    t++; q[t].id=t; q[t].ID=z; q[t].x=x2; q[t].y=y1-1; q[t].del=-1; q[t].opt=2;}int main(){    W=read();    t=0; z=0;    while (1)        {            int opt=read(); if (opt==3) break;            if (opt==1) {t++; q[t].x=read(),q[t].y=read(),q[t].del=read(),q[t].id=t,q[t].opt=1;}            if (opt==2) {int x1=read(),y1=read(),x2=read(),y2=read(); PreWork(x1,y1,x2,y2);}        }    sort(q+1,q+t+1);//    for (int i=1; i<=t; i++) printf("%d %d %d %d %d\n",q[i].id,q[i].opt,q[i].del,q[i].x,q[i].y);    CDQ(1,t);    for (int i=1; i<=z; i++) printf("%d\n",ans[i]);    return 0;}

 

【BZOJ-1176&2683】Mokia&简单题 CDQ分治


联系
我们