HFUT-1363 木条染色【线段树+离散化】

Description

小明是一个非常浪漫的画家，他喜欢画各种奇奇怪怪的画，虽然没人理解他画的究竟是什么东西。
有一天，他突发奇想，对于一根木条，他每次从木条中选取一个区间[l,r]进行染色，经过多次染色后，他想知道在[a,b]区间中有几个未被染色的子区间？

可惜小明虽然画画非常厉害，但是并不擅长解决这类问题，于是，他拿着这根木条来找你，希望你能够给他帮助。

假设木条无限长，所有查询都在木条长度范围内，未被染色的子区间是指，木条上染过色的区间的间断部分。

Input

第一行一个整数T，代表数据组数。
对于每组数据，第一行给出两个整数n，q，分别代表染色的区间个数，以及查询个数。

之后n行，每行两个整数l，r，表示将l到r的区间进行染色，包含l，r两个节点。

之后q行，每行两个整数a，b，表示询问a到b总共有多少未被染色的子区间。

两组数据之间用一个空行隔开。

T<20

n<10000

q<100000

0<=l<r<1000000

0<=a<=b<1000000

Output

对于每次询问，输出一个整数，表示查询结果。
每组数据之后，请输出一个空行。

Sample Input

2
2 3
1 2
3 4
1 3
3 4
5 5
3 3
1 5
2 8
5 6
0 5
0 9
9 9

Sample Output

1
0
1

1
2
1

Hint

对于第一组数据，[0,1)，(2,3)，(4,+)是未染色的子区间，因此查询[1,3]可以找到(2,3)这个子区间，而对于[3,4]不能找到，对于[5,5]可以找到[5,5]。对于第二组数据，[0,1)和(8,+)是未染色的子区间，因此对于[0,5]只有子区间[0,1)，对于查询[0,9]，有子区间[0,1)和（8,9]，对于查询[9,9]，有[9,9]这个子区间。

题解：

题目比较简单，一般的区间更新+离散化，主要题意很迷，区间[1,1]当做一个点，[1,2]也当做一个点，看洋少的写法换了种离散化的方法结果调bug调半天

代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define INF 0x3f3f3f3f
 4 #define M(a, b) memset(a, b, sizeof(a))
 5 #define lson o<<1
 6 #define rson o<<1|1
 7 const int N = 100000 + 5;
 8 int Hash[1000005], val[1000005], a[N], L[N], R[N], qL, qR, tot, num;
 9 
10 void build(int o, int L, int R) {
11     val[o] = 1;
12     if (L == R) return;
13     int M = (L + R) >> 1;
14     build(lson, L, M);
15     build(rson, M+1, R);
16 }
17 
18 void pushup(int o) {
19     if (val[lson] == val[rson]) val[o] = val[lson];
20     else val[o] = -1;
21 }
22 
23 void pushdown(int o) {
24     if (val[o] != -1) val[lson] = val[rson] = val[o];
25 }
26 
27 void update(int o, int L, int R) {
28     if (qL <= L && R <= qR) {
29         val[o] = 0;
30     }
31     else {
32         pushdown(o);
33         int M = (L + R) >> 1;
34         if (qL <= M) update(lson, L, M);
35         if (M < qR) update(rson, M+1, R); 
36         pushup(o);
37     }
38 }
39 
40 int query(int o, int L, int R) {
41     int ans = 0;
42     if (val[o] != -1) return val[o];
43     int M = (L + R) >> 1;
44     if (qL <= M) ans += query(lson, L, M);
45     if (M < qR) ans += query(rson, M+1, R);
46     return ans;
47 }
48 
49 void getHash(int n) {
50     M(Hash, 0);
51     tot = 2;
52     sort(a, a+2*n);
53     Hash[a[0]] = tot;
54     for (int i = 1; i < 2*n; ++i)
55         if (a[i] > a[i-1]) {tot += 2; Hash[a[i]] = tot;}
56     num = 1;
57     for (int i = 0; i <= a[2*n-1]+2; ++i)
58         if (Hash[i]) num = Hash[i] + 1;
59         else Hash[i] = num; 
60 }
61 
62 int main() {
63     int T, n, q;
64     scanf("%d", &T);
65     while (T--) {
66         scanf("%d%d", &n, &q);
67         for (int i = 0; i < n; ++i) {
68             scanf("%d%d", &a[2*i], &a[2*i+1]);
69             L[i] = a[2*i];
70             R[i] = a[2*i+1];
71         }
72         getHash(n);
73         build(1, 1, num);
74         int l, r;
75         for (int i = 0; i < n; ++i) {
76             qL = Hash[L[i]]; qR = Hash[R[i]];
77             update(1, 1, num);
78         }
79         for (int i = 0; i < q; ++i) {
80             scanf("%d%d", &l, &r);
81             r = min(a[2*n-1]+2, r);
82             qL = Hash[l]; qR = Hash[r];
83             printf("%d
", query(1, 1, num));
84         }
85         if (T) printf("
");
86     }
87 
88     return 0;
89 }

HFUT-1363 木条染色 【线段树+离散化】

HFUT-1363 木条染色【线段树+离散化】