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
| #include <bits/stdc++.h> using namespace std; typedef long long LL; const int MAX_N = 1000 + 5; int T, n, m, d[MAX_N * 4], opL[MAX_N], opR[MAX_N], tot, dL[MAX_N], dR[MAX_N]; int bsz, bt, lb[MAX_N], rb[MAX_N], blk[MAX_N * 4], tag[MAX_N], a[MAX_N * 4]; int main() { scanf("%d", &T); for (int cs = 1; cs <= T; ++cs) { scanf("%d%d", &n, &m); tot = 0; d[++tot] = 0; d[++tot] = n; for (int i = 1; i <= m; ++i) { scanf("%d%d", opL + i, opR + i); d[++tot] = opL[i]; d[++tot] = opL[i] - 1; d[++tot] = opR[i]; d[++tot] = opR[i] - 1; } sort(d + 1, d + tot + 1); tot = unique(d + 1, d + tot + 1) - d - 1; for (int i = 1; i <= m; ++i) { dL[i] = lower_bound(d + 1, d + tot + 1, opL[i]) - d; dR[i] = lower_bound(d + 1, d + tot + 1, opR[i]) - d; } bsz = ceil(int(sqrt(tot))); bt = 0; int bl, br; for (bl = 1; bl <= tot; bl = br + 1) { br = min(tot, bl + bsz - 1); ++bt; lb[bt] = bl; rb[bt] = br; tag[bt] = 0; for (int i = bl; i <= br; ++i) { blk[i] = bt; a[i] = 0; } } int sb, eb; for (int q = 1; q <= m; ++q) { sb = blk[dL[q]]; eb = blk[dR[q]]; if (sb == eb) { for (int i = dL[q]; i <= dR[q]; ++i) ++a[i]; continue; } for (int i = dL[q]; i <= rb[sb]; ++i) ++a[i]; for (int i = sb + 1; i < eb; ++i) ++tag[i]; for (int i = lb[eb]; i <= dR[q]; ++i) ++a[i]; } int cnt = 0, tl, tr, len; for (int i = 1; i <= tot; ++i) { if ((a[i] + tag[blk[i]]) & 1) { tl = d[i - 1] + 1; tr = d[i]; len = max(tr - tl + 1, 0); cnt += len; } } printf("Case #%d: %d\n", cs, cnt); } return 0; }
|