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
|
#define N 10010
#define debug cerr << "Passing " << __FUNCTION__ << " line " <<__LINE__ << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
inline void (int& x) {
x = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar());
for (; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
}
int T, n, k;
int lazy[N << 2], sumv[N << 2];
inline void pushdown(int o, int L, int R) {
if (lazy[o]) {
int M = (L + R) >> 1;
sumv[o << 1] = (M - L + 1) - sumv[o << 1];
sumv[o << 1 | 1] = (R - M) - sumv[o << 1 | 1];
lazy[o << 1] ^= 1, lazy[o << 1 | 1] ^= 1;
lazy[o] = 0;
}
}
inline void build(int o, int L, int R) {
lazy[o] = 0;
if (L == R) {
sumv[o] = 0;
return;
}
int M = (L + R) >> 1;
build(o << 1, L, M);
build(o << 1 | 1, M + 1, R);
sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
}
inline void update(int o, int L, int R, int l, int r) {
if (l <= L && r >= R) {
sumv[o] = (R - L + 1) - sumv[o];
lazy[o] ^= 1;
return;
}
pushdown(o, L, R);
int M = (L + R) >> 1;
if (l <= M) update(o << 1, L, M, l, r);
if (r > M) update(o << 1 | 1, M + 1, R, l, r);
sumv[o] = sumv[o << 1] + sumv[o << 1 | 1];
}
inline int query(int o, int L, int R, int l, int r) {
if (l <= L && r >= R) return sumv[o];
pushdown(o, L, R);
int M = (L + R) >> 1, ret = 0;
if (l <= M) ret += query(o << 1, L, M, l, r);
if (r > M) ret += query(o << 1 | 1, M + 1, R, l, r);
return ret;
}
struct Line {
int x, d, u;
Line() {}
Line(int x, int d, int u) : x(x), d(d), u(u) {}
bool operator<(const Line& rhs) const { return x < rhs.x; }
} add[N], del[N];
int main() {
read(T);
while (T--) {
read(n), read(k);
build(1, 1, n);
for (int i = 1, l, r, d, u; i <= k; ++i) {
read(l), read(r), read(d), read(u);
if (l > r) swap(l, r);
if (d > u) swap(d, u);
add[i] = Line(l, d, u);
del[i] = Line(r, d, u);
}
sort(add + 1, add + k + 1);
sort(del + 1, del + k + 1);
int ret = 0;
for (int i = 1, p = 1, q = 1; i <= n; ++i) {
for (; p <= k && add[p].x == i; ++p) update(1, 1, n, add[p].d, add[p].u);
ret += query(1, 1, n, 1, n);
for (; q <= k && del[q].x == i; ++q) update(1, 1, n, del[q].d, del[q].u);
}
printf("%dn", ret);
}
return 0;
}
|
近期评论