1176: [Balkan2007]Mokia
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范围
CDQ分治
首先提一个求矩阵和的经典思路：
将矩阵转化成 由1,1为左下角的矩阵 的 和差
即矩阵[x1,y1,x2,y2] (以左下角和右上角点的坐标表示矩阵)
可表示为[x1,y1,x2,y2] = [1,1,x2,y2] - [1,1,x1 -1,y2] - [1,1,x2,y2 -1] + [1,1,x1 -1,y1 -1]
所以这道题求矩阵和即可转化为求四个以（1,1）为坐下角的矩阵
一个位置的点(a,b)对某矩阵[1,1,x,y]的和有贡献
当且仅当满足 a <= x 且 b <= y
而对于每个修改操作，可以理解为增加某一点对其余点的贡献
所以 这道题就可以完美地转化为 BZOJ3262 了
最后一点不同就是，3262的每个操作既是添加，也是询问
本题的操作有单独的添加和询问之分
只有在二分左半段有一添加操作时，添加
只有在二分右半段有一询问操作是，询问
然后，没有了。。。
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 200010;
const int MaxW = 2000010;
int W, S, N;
struct opt{
int o, x, y, key, k;
opt (int p = 0,int a = 0, int b = 0, int s = 0, int w = 0) {
o = p; x = a; y = b; key = s; k = w;
}
}p[MaxN],q[MaxN];
int sum[MaxW];
inline int lowbit(int x){
return x & -x;
}
inline void New(int x){
for (; x <= W; x += lowbit(x))
if (sum[x]) sum[x] = 0;
else break;
}
inline void Insert(int x, int k){
for (; x <= W; x += lowbit(x))
sum[x] += k;
}
inline int Query(int x){
int res = 0;
for (; x; x -= lowbit(x))
res += sum[x];
return res;
}
inline void solve(int l, int r){
if (l == r) return;
int mid = l + r >> 1;
solve(l, mid), solve(mid + 1, r);
int t1 = l, t2 = mid + 1;
for (int i = l; i <= r; ++i)
if (t1 <= mid && p[t1].x <= p[t2].x || t2 > r) {
q[i] = p[t1++];
if (q[i].o % 2) Insert(q[i].y, q[i].key);
}
else {
q[i] = p[t2++];
if (!(q[i].o % 2)) q[i].key += Query(q[i].y);
}
for (int i = l; i <= r; ++i)
p[i] = q[i], New(q[i].y);
}
bool cmp (const opt &a, const opt &b){
return a.k < b.k;
}
int main(){
scanf("%d%d", &S, &W);
for (;;){
int o, x1, y1, x2, y2, k;
scanf("%d",&o);
if (o == 3) break;
if (o % 2) {
scanf("%d%d%d", &x1, &y1, &k);
p[++N] = opt(o, x1, y1, k, N);
}
else {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
p[++N] = opt(o, x1 - 1, y1 - 1, 0, N);
p[++N] = opt(o, x2, y2, 0, N);
p[++N] = opt(o, x1 - 1, y2, 0, N);
p[++N] = opt(o, x2, y1 - 1, 0, N);
}
}
solve(1, N);
sort(p + 1, p + N + 1, cmp);
for (int i = 1; i <= N; )
if (!(p[i].o % 2)){
int x1 = p[i].x, y1 = p[i].y;
int x2 = p[i + 1].x, y2 = p[i + 1].y;
int ans = p[i].key + p[i + 1].key - p[i + 2].key -p[i + 3].key;
ans += (x2 - x1) * (y2 - y1) * S;
printf("%d\n",ans);
i += 4;
}
else ++i;
}
评论 (0)
