poj2528:线段树+离散化

2016年8月25日 0 条评论 1.33k 次阅读 0 人点赞

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

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

/*<br />
Source code<br />
Problem: 2528		User: aclolicon<br />
Memory: 2092K		Time: 79MS<br />
Language: G++		Result: Accepted</p>
<p>    Source code<br />
*/<br />
#include&lt;cstdio&gt;<br />
#include&lt;iostream&gt;<br />
#include&lt;algorithm&gt;<br />
#include&lt;cstring&gt;<br />
#define MAXN 40050<br />
#define INF 0x7f7f7f7f<br />
using namespace std;</p>
<p>int t, n, x, y, maxi, nc;<br />
int bef, bc, cnt, ans;<br />
bool color[MAXN];</p>
<p>struct tree{<br />
	int l, r, t, lazy;<br />
}node[MAXN * 2];</p>
<p>struct resort{<br />
	int ori, val, left;<br />
}re[MAXN];</p>
<p>struct poster{<br />
	int l, r;<br />
	void add(int v){<br />
		if (l == -1) l = v;<br />
		else r = v;<br />
		if (l &gt; r) swap(l, r);<br />
		maxi = r == INF? maxi: max(maxi, r);<br />
	}<br />
}p[MAXN];</p>
<p>bool cmp(resort a, resort b){<br />
	return a.val &lt; b.val;<br />
}</p>
<p>void pushdown(int i){<br />
	if (node[i].t == 0) return;<br />
	if (node[i].l &lt; node[i].r){<br />
		node[i &lt;&lt; 1].t = node[i].t;<br />
		node[(i &lt;&lt; 1) + 1].t = node[i].t;<br />
	}<br />
	node[i].t = 0;<br />
}</p>
<p>void getans(int i){<br />
	if (node[i].t != 0 &amp;&amp; color[node[i].t] == 0){<br />
		color[node[i].t] = 1;<br />
		ans++;<br />
		return;<br />
	}<br />
	if (node[i].t != 0) return;<br />
	if (node[i].l == node[i].r) return;<br />
	getans((i &lt;&lt; 1));<br />
	getans((i &lt;&lt; 1) + 1);<br />
}</p>
<p>void build(int i, int l, int r){<br />
	node[i].l = l;<br />
	node[i].r = r;<br />
	node[i].t = 0;<br />
	if (r - l &gt; 0){<br />
		int mid = (l + r) &gt;&gt; 1;<br />
		build((i &lt;&lt; 1), l, mid);<br />
		build((i &lt;&lt; 1) + 1, mid + 1, r);<br />
	}<br />
}</p>
<p>void update(int i, int l, int r, int v){<br />
	int nowl = node[i].l;<br />
	int nowr = node[i].r;<br />
	if (nowl &gt; r || nowr &lt; l) return;<br />
	if (l &lt;= nowl &amp;&amp; r &gt;= nowr){<br />
		node[i].t = v;<br />
		return;<br />
	}<br />
	pushdown(i);<br />
	update((i &lt;&lt; 1), l, r, v);<br />
	update((i &lt;&lt; 1) + 1, l, r, v);<br />
	return;<br />
}</p>
<p>void trans(){<br />
	sort(re, re + cnt, cmp);<br />
	p[re[0].ori].add(1);<br />
	bc = 0;<br />
	for (int i = 1; i &lt; cnt; i++){<br />
		if (re[i - 1].val == re[i].val){//看是否和之前的值相等<br />
			bc++;<br />
		}<br />
		if (re[i - 1].left  == 0 &amp;&amp; re[i].left == 1 &amp;&amp; re[i - 1].val != re[i].val &amp;&amp; re[i - 1].val != re[i].val - 1){<br />
			bc--;<br />
		}<br />
		p[re[i].ori].add(i - bc + 1);</p>
<p>	}<br />
}</p>
<p>void init(){<br />
	scanf(&quot;%d&quot;, &amp;n);<br />
	cnt = 0;<br />
	nc = 0, maxi = 0;<br />
	for (int i = 0; i &lt; n; i++){<br />
		scanf(&quot;%d%d&quot;, &amp;x, &amp;y);<br />
		p[i].l = -1, p[i].r = INF;<br />
		re[cnt].ori = i;<br />
		re[cnt].left = 1;<br />
		re[cnt++].val = x;<br />
		re[cnt].ori = i;<br />
		re[cnt].left = 0;<br />
		re[cnt++].val = y;<br />
	}<br />
}</p>
<p>int main(){<br />
	scanf(&quot;%d&quot;, &amp;t);<br />
	while(t--){<br />
		memset(color, 0, sizeof(color));<br />
		init();<br />
		trans();<br />
		build(1, 1, maxi);<br />
		for (int i = 0; i &lt; n; i++){<br />
			update(1, p[i].l, p[i].r, i + 1);<br />
		}<br />
		ans = 0;<br />
		getans(1);<br />
		printf(&quot;%d\n&quot;, ans);<br />
	}<br />
}           

b-a

这个人太懒什么东西都没留下

文章评论(0)