BZOJ1176 Mokia

发表于

  题意:一个矩阵，最开始所有值都是0。2种操作:

  1、将$(x, y)$位置的值增加a

  2、查询左下角$(x_1, y_1)$，右上角$(x_2, y_2)$子矩阵权值和

  第一道cdq分治的题目。
  对于一次矩阵操作，我们可以通过线段树套线段树在$O(\log^2 n)$的时间内处理。这样复杂度是正确的，但是有没有更简便的，不用大数据结构的方法？cdq分治便可以解决这样的一个问题。
  cdq分治主要运用于离线数据方面，其主要作用可以说是破除查询与修改的时间限制，让查询与修改能够以一个更好的顺序呈现出来，更加方便地被处理。
  拿这道题来说吧。如果所有查询都在修改之后，那么这道题有没有更加简便的做法？首先对于2操作，我们可以用矩阵的二维差分来将其转化为查询右上角为$(x, y)​$的前缀矩阵和。然后我们将所有的查询和修改放在一起按$x​$坐标排序，$x​$相同的按$y​$排序，使用一个树状数组记录$y​$坐标信息，当每次扫到一个修改操作时，就把它的修改放到树状数组中，当每次扫到一个查询操作时，由于我们知道修改都在查询之前，于是前面扫到过的修改操作就是所有有可能影响该查询的修改操作。于是我们直接在树状数组里寻找想要的信息即可。
  可是题目没有这个条件。那么我们是否可以”变出”这个条件呢？这就是cdq分治的精髓所在。我们将所有的操作按时间排序，接下来，分治这个时间轴。在一个分治区间$[l, r]$中，我们将$[l, mid]$时间内发生的修改操作与$[mid, r]$时间内发生的查询操作拿出来，显然这些提出来的修改操作都在查询操作之前，那么我们就可以用上面的方法更新查询操作了。那么这样就完了吗？对于一个发生在时间点$k(k > mid)$的查询操作，区间$[mid + 1, k - 1]$中的修改操作也可能会对其造成影响。所以继续分治下去就好。
  每次分治完别忘了还原临时信息，比如树状数组。
  注意清树状数组直接一步一步撤回之前操作，不能用memset，不然复杂度是错的！

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
#define rep(i, l, r) for(int i = l, i##end = r; i <= i##end; ++i)
#define drep(i, l, r) for(int i = l, i##end = r; i >= i##end; --i)
#define ms(a, b) memset(a, b, sizeof a);
template<class T> inline bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template<class T> inline bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline T& read(T& x)
{
    static char c; bool flag = 0;
    while(!isdigit(c = getchar())) if(c == '-') flag = 1;
    for(x = c - '0'; isdigit(c = getchar()); (x *= 10) += c - '0');
    if(flag) x = -x; return x;
}
const int maxn = 2000010, maxm = 640010, maxq = 10010;
int n, s;
int ans[maxq];
struct data
{
	int op, t, id, x, y, w;
	data() { }
	data(int _op, int _t, int _id, int _x, int _y, int _w): op(_op), t(_t), id(_id), x(_x), y(_y), w(_w) { }
	bool operator < (const data& rhs) const
	{
		return x != rhs.x ? x < rhs.x : y != rhs.y ? y < rhs.y : op < rhs.op;
	}
} c[maxm], tmp[maxm];
int cur;
namespace BIT
{
	int T[maxn];
	void add(int p, int x) { for(; p <= n; p += p & -p) T[p] += x; }
	int query(int p) { int ret = 0; for(; p; p -= p & -p) ret += T[p]; return ret; }
}
using namespace BIT;
void solve(int l, int r)
{
	if(l == r) return;
	int mid = l + r >> 1;
	rep(i, l, r)
		if(c[i].op == 1 && c[i].t <= mid) add(c[i].y, c[i].w);
		else if (c[i].op == 2 && c[i].t > mid) ans[c[i].id] += c[i].w * query(c[i].y);
	rep(i, l, r) if(c[i].op == 1 && c[i].t <= mid) add(c[i].y, -c[i].w);
	int cur1 = l, cur2 = mid + 1;
	rep(i, l, r)
		if(c[i].t <= mid) tmp[cur1++] = c[i];
		else tmp[cur2++] = c[i];
	rep(i, l, r) c[i] = tmp[i];
	solve(l, mid); solve(mid + 1, r);
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("exec.in", "r", stdin); freopen("exec.out", "w", stdout);
#endif
	read(s); read(n);
	int op, q = 0;
	while(read(op) != 3)
	{
		if(op == 1)
		{
			int x, y, w;
			read(x); read(y); read(w);
			c[++cur] = data(1, cur, 0, x, y, w);
		}
		else
		{
			int x1, y1, x2, y2; ++q;
			read(x1), read(y1), read(x2), read(y2);
			c[++cur] = data(2, cur, q, x2, y2, 1);
			c[++cur] = data(2, cur, q, x1 - 1, y2, -1);
			c[++cur] = data(2, cur, q, x2, y1 - 1, -1);
			c[++cur] = data(2, cur, q, x1 - 1, y1 - 1, 1);
		}
	}
	sort(c + 1, c + cur + 1);
	solve(1, cur);
	rep(i, 1, q) printf("%d\n", ans[i]);
	return 0;
}