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
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
5
HINT
保证答案不会超过int范围
Source
2683: 简单题
Time Limit: 50 Sec Memory Limit: 128 MB
Submit: 821 Solved: 339
[Submit][Status][Discuss]
Description
|
命令 |
参数限制 |
内容 |
|
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
Output
Sample Input
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3
Sample Output
5
HINT
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=; char ch=getchar();
while (ch<'' || ch>'') {ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x;
}
#define MAXQ 200010
#define MAXN 500010
int 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=; 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<<],tmp[MAXQ<<];
void CDQ(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>,z1=l,z2=mid+;
for (int i=l; i<=r; i++)
{
if (q[i].opt== && q[i].id<=mid) BIT::Change(q[i].y,q[i].del);
if (q[i].opt== && 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== && 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+,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-; q[t].y=y1-; q[t].del=; q[t].opt=;
t++; q[t].id=t; q[t].ID=z; q[t].x=x2; q[t].y=y2; q[t].del=; q[t].opt=;
t++; q[t].id=t; q[t].ID=z; q[t].x=x1-; q[t].y=y2; q[t].del=-; q[t].opt=;
t++; q[t].id=t; q[t].ID=z; q[t].x=x2; q[t].y=y1-; q[t].del=-; q[t].opt=;
}
int main()
{
W=read();
t=; z=;
while ()
{
int opt=read(); if (opt==) break;
if (opt==) {t++; q[t].x=read(),q[t].y=read(),q[t].del=read(),q[t].id=t,q[t].opt=;}
if (opt==) {int x1=read(),y1=read(),x2=read(),y2=read(); PreWork(x1,y1,x2,y2);}
}
sort(q+,q+t+);
// 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(,t);
for (int i=; i<=z; i++) printf("%d\n",ans[i]);
return ;
}