poj2528(离散化+线段树)

点击打开题目链接

大意：n（n<=10000)个人依次贴海报,给出每张海报所贴的范围li,ri(1<=li<=ri<=10000000)。

          求出最后还能看见多少张海报。

思路：离散化，根据所输数据处理，分成len段。然后对于各个海报，二分求得其占据第a段到第b段。

           然后，利用线段树，区间染色（比如第i张海报，相当于在区间上染色i）。

           最后，求出所有区间上不同颜色数。

代码如下：

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.StringTokenizer;
import java.util.TreeSet;
class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer;
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
public class Main {
/**
* @param args
*/
static int t, n, len, l, r, mid, ans;
static int num[], nownum[], larr[], rarr[];
static boolean bo[];
static TreeSet<Integer> treeSet;
private static void pushdown(int o) {
if (nownum[o] > 0) {
nownum[o * 2] = nownum[o];
nownum[o * 2 + 1] = nownum[o];
nownum[o] = 0;
}
}
private static void update(int o, int l, int r, int ul, int ur, int num) {
if ((ul <= l) && (ur >= r)) {
nownum[o] = num;
return;
}
pushdown(o);
int mid = (l + r) / 2;
if (ul <= mid)
update(o * 2, l, mid, ul, ur, num);
if (ur > mid)
update(o * 2 + 1, mid + 1, r, ul, ur, num);
}
private static void paint(int o, int l, int r) {
if (nownum[o] > 0) {
bo[nownum[o]] = true;
return;
}
if (l == r)
return;
int mid = (l + r) / 2;
paint(o * 2, l, mid);
paint(o * 2 + 1, mid + 1, r);
}
private static int find(int fnum) {
int l = 0;
int r = len;
while (r - l > 1) {
int mid = (l + r) / 2;
if (num[mid] < fnum)
l = mid;
else
r = mid;
}
return r;
}
private static void deal() {
Iterator<Integer> iter = treeSet.iterator();
len = 0;
while (iter.hasNext()) {
len++;
num[len] = iter.next();
}
bo = new boolean[n + 1];
nownum = new int[4 * len];
for (int i = 1; i <= n; i++) {
l = find(larr[i]);
r = find(rarr[i] + 1) - 1;
// 第n段,num[n]~num[n+1]
update(1, 1, len - 1, l, r, i);
}
paint(1, 1, len - 1);
ans = 0;
for (int i = 1; i <= n; i++)
if (bo[i])
ans++;
System.out.println(ans);
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
Reader.init(System.in);
t = Reader.nextInt();
treeSet = new TreeSet<Integer>();
num = new int[40002];
for (int casenum = 1; casenum <= t; casenum++) {
n = Reader.nextInt();
larr = new int[n + 1];
rarr = new int[n + 1];
treeSet.clear();
treeSet.add(1);
for (int i = 1; i <= n; i++) {
larr[i] = Reader.nextInt();
rarr[i] = Reader.nextInt();
treeSet.add(larr[i]);
treeSet.add(rarr[i] + 1);
}
deal();
}
}
}

最后

以上就是淡定黑裤为你收集整理的poj2528(离散化+线段树)的全部内容，希望文章能够帮你解决poj2528(离散化+线段树)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。