bzoj1176

题意

维护一个W*W的矩阵,初始值均为S.每次操作可以增加某格子的权值,或询问某子矩阵的总权值.修改操作数M<=160000,询问数Q<=10000,W<=2000000.

分析

维护矩阵和的基本思想还是不变的,即利用二维前缀和。 困难在于W过大,无法直接开数组。

考虑分治

设$solve(l,r)$ 为只考虑第l个到第r个操作/询问内,所有操作对询问的影响。

那么我们分治步骤即为

  1. 将数组按x坐标排序
  2. 计算solve(l,r) , 按坐标mid将数组分为两块
  3. $solve(l,mid)$
  4. 计算[l,mid]操作对[mid+1,r]的询问产生的影响
  5. $solve(mid+1,r)$
  6. 将数组还原成按x排序的

那么如何做步骤4呢?

我们按照x坐标排序,用权值线段树或者权值树状数组来维护y方向的权值。

当然这么写常数比较大。 我们可以在分治之前先解决步骤4, 这样就不需要步骤6了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
// ybmj
#include <bits/stdc++.h>
using namespace std;
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define lson_len (len - (len >> 1))
#define rson_len (len >> 1)
#define pb(x) push_back(x)
#define clr(a, x) memset(a, x, sizeof(a))
#define mp(x, y) make_pair(x, y)
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define my_unique(a) a.resize(distance(a.begin(), unique(a.begin(), a.end())))
#define my_sort_unique(c) (sort(c.begin(), c.end())), my_unique(c)
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const int maxn = 2e5 + 5;
const int maxm = 2e6 + 5;
struct P {
int op, x, y, val, id, qid;
bool operator<(const P& A) const { return x < A.x; }
};
P a[maxn << 2], tmp[maxn << 2];
int ans[maxn];
int BIT[maxm];
int n, s, w;
inline int lowb(int x) { return x & (-x); }
inline int query(int l, int r) {
int ret = 0;
for (int i = l - 1; i > 0; i -= lowb(i)) ret -= BIT[i];
for (int i = r; i > 0; i -= lowb(i)) ret += BIT[i];
return ret;
}
inline void update(int x, int y) {
for (int i = x; i <= w; i += lowb(i)) BIT[i] += y;
}

void solve(int l, int r) {
if (l == r) return;
int mid = l + r >> 1;
int l1 = l, l2 = mid + 1;
for (int i = l; i <= r; i++) {
if (a[i].id <= mid)
tmp[l1++] = a[i];
else
tmp[l2++] = a[i];
}
for (int i = l; i <= r; i++) a[i] = tmp[i];
solve(l, mid);

l1 = l;
for (int i = mid + 1; i <= r; i++) {
while (l1 <= mid && a[l1].x <= a[i].x) {
if (a[l1].op == 1) update(a[l1].y, a[l1].val);
l1++;
}
if (a[i].op == 1) continue;
ans[a[i].qid] += a[i].val * query(1, a[i].y);
}
for (int i = l; i < l1; i++) {
if (a[i].op == 1) update(a[i].y, -a[i].val);
}

solve(mid + 1, r);

l1 = l, l2 = mid + 1;
int l3 = l;
while (l1 <= mid && l2 <= r) {
if (a[l1].x > a[l2].x)
tmp[l3++] = a[l2++];
else
tmp[l3++] = a[l1++];
}
while (l1 <= mid) tmp[l3++] = a[l1++];
while (l2 <= r) tmp[l3++] = a[l2++];
for (int i = l; i <= r; i++) a[i] = tmp[i];
}
int main() {
// /*
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
// */
std::ios::sync_with_stdio(false);
scanf("%d%d", &s, &w);
clr(ans, -1);
int op, x1, x2, y1, y2, val;
n = 0;
int cnt = 0;
while (true) {
scanf("%d", &op);
if (op == 3) break;
if (op == 1) {
scanf("%d%d%d", &x1, &y1, &val);
a[++n] = {op, x1, y1, val, n, -1};
} else {
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
++cnt;
ans[cnt] = 0;
a[++n] = {op, x2, y2, 1, n, cnt};
a[++n] = {op, x1 - 1, y2, -1, n, cnt};
a[++n] = {op, x2, y1 - 1, -1, n, cnt};
a[++n] = {op, x1 - 1, y1 - 1, 1, n, cnt};
}
}
sort(a + 1, a + n + 1);
solve(1, n);
for (int i = 1; i <= cnt; i++) {
if (ans[i] == -1)
continue;
else
printf("%d\n", ans[i]);
}
}
Thank you for your support!