poj2528:线段树+离散化

http://poj.org/problem?id=2528
题意：
给出几条线段，求按顺序覆盖之后能看到得线段数目。
解法：
线段树+离散化：
但是离散化有几个问题要注意：
我建的是段树，也就是：

|____|____|____|
  1    2    3

这样子的。
2,3,4那组数据中比较有争议的一组是：

如果不离散化直接算覆盖的话，是这样的：（暂且忽略前面的1-4..）

...          |____|____|____|
               6     7   8
   |____|____|
     4    5   
        |____|____|
          5    6

显然答案为2啦。（从顶往底看，注意输入顺序）
然后离散化之后,
如果不注意数值相同，就会变成这样：

3 4
1 2
5 6

数值相同后离散就是这样:

2 3
1 2
3 4

          |____|____|
            3     4  
|____|____|
  1    2   
     |____|____|
       2    3

这就对了。

但是，离散化得再注意到下面这个问题：

1 10
1 3
6 10

这组数据，不离散化是这样的：

                         |____|____|____|____|____|
                           6    7    8    9    10
|____|____|____|
  1    2    3
|____|____|____|____|____|____|____|____|____|____|
  1    2    3    4    5    6    7    8    9    10

显然答案为3.
如果我们使用上面的“注意到数值相同的离散化”，结果是这样的：

1 4
1 2
3 4

画出来是这样的：

          |____|____|
            3    4
|____|____|
  1    2   
|____|____|____|____|
  1    2    3    4

然后坑就出现了..
我的解决方案是，

             ↓
          |____|____|
        ↓   3    4
|____|____|
  1    2   
|____|____|____|____|
  1    2    3    4

在离散化时出现了海报右端序号在前，左端序号在后，且序号不等（也就是离散后会相邻的情况）：

             ↓
          |____|____|
        ↓   3    4
|____|____|
  1    2

这两个就属于离散化后相邻的情况
我加上1：
变成这样：

1 5
1 2
4 5

               |____|____|
                 4    5
|____|____|
  1    2   
|____|____|____|____|____|
  1    2    3    4    5

可能会有人问，要是是这样的呢？

本来就相邻的情况呢？
这样的话，提取原来的序号，比较原本是否就相邻即可。
第一次写离散化...有错请指正
[code lang="cpp"]/*
Source code
Problem: 2528 User: aclolicon
Memory: 2092K Time: 79MS
Language: G++ Result: Accepted

Source code
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define MAXN 40050
#define INF 0x7f7f7f7f
using namespace std;

int t, n, x, y, maxi, nc;
int bef, bc, cnt, ans;
bool color[MAXN];

struct tree{
int l, r, t, lazy;
}node[MAXN * 2];

struct resort{
int ori, val, left;
}re[MAXN];

struct poster{
int l, r;
void add(int v){
if (l == -1) l = v;
else r = v;
if (l > r) swap(l, r);
maxi = r == INF? maxi: max(maxi, r);
}
}p[MAXN];

bool cmp(resort a, resort b){
return a.val < b.val;
}

void pushdown(int i){
if (node[i].t == 0) return;
if (node[i].l < node[i].r){
node[i << 1].t = node[i].t;
node[(i << 1) + 1].t = node[i].t;
}
node[i].t = 0;
}

void getans(int i){
if (node[i].t != 0 && color[node[i].t] == 0){
color[node[i].t] = 1;
ans++;
return;
}
if (node[i].t != 0) return;
if (node[i].l == node[i].r) return;
getans((i << 1));
getans((i << 1) + 1);
}

void build(int i, int l, int r){
node[i].l = l;
node[i].r = r;
node[i].t = 0;
if (r - l > 0){
int mid = (l + r) >> 1;
build((i << 1), l, mid);
build((i << 1) + 1, mid + 1, r);
}
}

void update(int i, int l, int r, int v){
int nowl = node[i].l;
int nowr = node[i].r;
if (nowl > r || nowr < l) return;
if (l <= nowl && r >= nowr){
node[i].t = v;
return;
}
pushdown(i);
update((i << 1), l, r, v);
update((i << 1) + 1, l, r, v);
return;
}

void trans(){
sort(re, re + cnt, cmp);
p[re[0].ori].add(1);
bc = 0;
for (int i = 1; i < cnt; i++){
if (re[i - 1].val == re[i].val){//看是否和之前的值相等
bc++;
}
if (re[i - 1].left == 0 && re[i].left == 1 && re[i - 1].val != re[i].val && re[i - 1].val != re[i].val - 1){
bc--;
}
p[re[i].ori].add(i - bc + 1);

}
}

void init(){
scanf("%d", &n);
cnt = 0;
nc = 0, maxi = 0;
for (int i = 0; i < n; i++){
scanf("%d%d", &x, &y);
p[i].l = -1, p[i].r = INF;
re[cnt].ori = i;
re[cnt].left = 1;
re[cnt++].val = x;
re[cnt].ori = i;
re[cnt].left = 0;
re[cnt++].val = y;
}
}

int main(){
scanf("%d", &t);
while(t--){
memset(color, 0, sizeof(color));
init();
trans();
build(1, 1, maxi);
for (int i = 0; i < n; i++){
update(1, p[i].l, p[i].r, i + 1);
}
ans = 0;
getans(1);
printf("%d\n", ans);
}
} [/code]

poj2528:线段树+离散化

Comments

No comments found.