poj2528 线段树+骚气的离散化姿势

Posted by Cww97 on 2017-07-06

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/74515888
by cww97

这里写图片描述
这里写图片描述

因为这个图所以,不能当做左闭右开的线段树来做

and,卡了两个小时是因为

这个傻逼错误

1
2
3
4
5
6
7
8
9
10
11
12
//for (int i = 1; i <= A; i++) {
// x[a[i]] = i;//啊啊啊啊啊啊啊啊啊啊啊啊啊啊
//printf("x[%d] = %d\n", a[i], i);
//}

T.build(A);
for (int i = 1; i <= n; i++){
int L = lower_bound(a+1, a+A+1, l[i]) - a;//x[l[i]]
int R = lower_bound(a+1, a+A+1, r[i]) - a;//x[r[i]]
//printf("(%d, %d)\n", L, R);
T.update(L, R, i, 1, T.M+1,1);
}

妈的离散化忘了用lower_bound,还开数组存

发现错误前怀疑数据

发现错误后被自己蠢哭

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
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 7;

int l[N], r[N], n;
int a[N], A, x[N];
bool vis[N];
int ans;

struct segmentTree
{
#define lc (rt<<1)
#define rc (rt<<1^1)
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1^1
int M, col[N];

inline void build(int n){
M = 1; while(M<n)M<<=1; M--;
memset(col, 0, sizeof(col));
}

inline void pushDown(int rt){
if (col[rt] == 0) return;
col[lc] = col[rc] = col[rt];
col[rt] = 0;
}

inline void update(int L, int R, int x, int l, int r, int rt){
if (L <= l && r <= R){
col[rt] = x;
return;
}
pushDown(rt);
int m = (l + r) >> 1;
if (L <= m) update(L, R, x, lson);
if (m < R) update(L, R, x, rson);
}

inline int query(int rt){
if (col[rt] > 0) {
if (vis[col[rt]]) return 0;
vis[col[rt]] = 1;
return 1;
}
if (rt > M) return 0;
int ans = 0;
ans += query(lc);
ans += query(rc);
return ans;
}
} T;

int main(){
//freopen("in.txt", "r", stdin);
int _;
scanf("%d", &_);
for (;_--;){
scanf("%d", &n);
A = 0;
for (int i = 1; i <= n; i++){
scanf("%d%d", &l[i], &r[i]);
a[++A] = l[i];
a[++A] = r[i];
}
sort(a + 1, a + A+1);
A = unique(a + 1, a + A+1) - (a + 1);
for (int i = A; i > 1; i--){
if (a[i-1] + 1 < a[i]) a[++A] = a[i-1] + 1;
}
sort(a + 1, a + A+1);

T.build(A);
for (int i = 1; i <= n; i++){
int L = lower_bound(a+1, a+A+1, l[i]) - a;
int R = lower_bound(a+1, a+A+1, r[i]) - a;
T.update(L, R, i, 1, T.M+1,1);
}
ans = 0;
memset(vis, 0, sizeof(vis));
printf("%d\n", T.query(1));
}
return 0;
}
这里写图片描述
这里写图片描述