代码 学习

poj2528:线段树+离散化

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

|____|____|____|
  1    2    3

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

3
5 6
4 5
6 8

如果不离散化直接算覆盖的话,是这样的:(暂且忽略前面的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

可能会有人问,要是是这样的呢?

3
1 4
1 2
3 4

本来就相邻的情况呢?
这样的话,提取原来的序号,比较原本是否就相邻即可。
第一次写离散化...有错请指正

/*
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);
	}
}

b-a
我还没有学会写个人说明!
查看“b-a”的所有文章 →

Leave a Reply

Your email address will not be published. Required fields are marked *

相关推荐