[color=red]/*
Subject: Interval Tree
Author : a_clay
Created Date : 2012-02-05
Sample : poj 2528 贴海报 - 离散化经典
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define Bug cout << "here\n";
#define B(x) (x >> 1)
using namespace std;
const int N = 10005;
const int M = 10000010;
struct node {
int a, b;
int val; // 是否已经被覆盖
}t[16*N];
int n;
int pos[N][2];
int lag[4*N];
int kag[4*N];
int vis[4*N];
int ans;
int bfind(int n, int x) {
int l = 1, r = n;
while(l <= r) {
int mid = B(l+r);
if(kag[mid] == x) {
return mid;
}
else if(kag[mid] > x) {
r = mid-1;
}
else l = mid + 1;
}
}
void make_tree(int x, int y, int num) {
t[num].a = x;
t[num].b = y;
t[num].val = 0;
if(x == y) return;
else {
make_tree(x, B(x+y), 2*num);
make_tree(B(x+y)+1, y, 2*num+1);
}
}
void add(int x, int y, int c, int num) {
if(x <= t[num].a && t[num].b <= y) {
t[num].val = c; // 终止节点染色
return;
}
else {
int mid = B(t[num].a + t[num].b);
if(t[num].val > 0) {
t[2*num].val = t[num].val;
t[2*num+1].val = t[num].val;
t[num].val = 0;
}
if(x <= mid) {
add(x, y, c, 2*num);
}
if(y > mid) {
add(x, y, c, 2*num+1);
}
}
}
void query(int x, int y, int num) {
if(t[num].val > 0) {
int tc = t[num].val;
if(!vis[tc]) {
vis[tc] = 1;
ans++;
}
return;
}
else {
if(x == y) return;
query(x, B(x+y), 2*num);
query(B(x+y)+1, y, 2*num+1);
}
}
int main() {
int T, i;
scanf("%d", &T) ;
while(T--) {
memset(pos, 0, sizeof(pos));
memset(lag, 0, sizeof(lag)); // 辅助离散化
memset(kag, 0, sizeof(kag)); // 辅助离散化 的对应下标于
memset(vis, 0, sizeof(vis));
memset(t, 0, sizeof(t));
scanf("%d", &n);
int fn = 0;
for(i = 0; i < n; i++) {
scanf("%d%d", &pos[i][0], &pos[i][1]);
lag[++fn] = pos[i][0];
lag[++fn] = pos[i][1];
}
sort(lag+1, lag+fn+1);
fn = unique(lag+1, lag+fn + 1) - lag; //去掉重复元素 , 返回去重后的尾地址
fn = fn - 1;
int kn = 0;
for(i = 1; i <= fn; i++) { // 离散化
if(i > 1 && lag[i] > lag[i-1]+1) {
kag[++kn] = lag[i-1]+1;
}
kag[++kn] = lag[i];
}
make_tree(1, kn, 1);
for(i = 0; i < n; i++) {
int fx = bfind(kn, pos[i][0]);
int fy = bfind(kn, pos[i][1]);
add(fx, fy, i+1, 1); // i+1 为染色编号
}
ans = 0;
query(1, kn, 1);
printf("%d\n", ans);
}
return 0;
}[/color]
分享到:
相关推荐
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ2528-Mayor's posters 测试数据。数据来源:Alberta Collegiate Programming Contest 2003.10.18 – 问题G
西北工业大学-c语言-POJ-题目及答案-第七季.doc
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
不错的资源 收集了网上的一些解题报告 方便同学们学习参考
北大POJ2002-Squares 解题报告+AC代码
poj-2528 Mayor's posters 测试数据及答案
在进行ACM编程训练时做字符串专题的一些题目(POJ1782,POJ1790,POJ1951,POJ2003,POJ2121)
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
An solution of a problem using Splay Trees
NULL 博文链接:https://128kj.iteye.com/blog/1740501
NULL 博文链接:https://128kj.iteye.com/blog/1752345
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
北大POJ2305-Basic remains POJ2305-Basic remains
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
...
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3
北大POJ1321-Chess Problem POJ1321-Chess Problem