Mayor’s posters OpenJ_Bailian - 2528
题目 我就 不 写出来拉 ，简单 依据这道题 来简单的说一下 离散化算法。 离散化算法 是一种 将 许多 很大 的 空间 根据 这些空间 的相对关系 ，进行 离散化 ，将 这些大空间 转变为 与之 一一对应的 小空间 ，进而 减少 数据的大小 ，简化 运算。可以进行离散化 的 条件： 是 这些 大空间 在 运算中 与他们的 具体的大小 无关， 而只与他们 的先对 位置 有关 。 这道题 对应的 大空间 是 线段 ，由于 线段 的 范围很大 1 =》 10000000，而且 题目 的答案 只与这些线段 的相对 位置 有关 ，所以可以 对这些 线段 进行 离散化 ，下面 说一下 怎样 进行离散化：
这个 题 是要根据 线段树 来做的 ，可以根据 离散化 对数据 进行处理，其中 样例 的 数据 处理后为：（1， 4）， （2， 5）， （7， 8）， （3， 4）， （6， 8）
但是写到这里 ， 还有个问题 ，要怎么 用线段树 ，寻找 宣传海报的 的数量呢？ 我想了 一个方法 就是 当上面的数据 都处理 完之后， 不用 线段树更新 数据， 直接 查找数据， 而且还是 逆序 输入数据 ， 具体 过程见下面的 代码！
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;int n;
int pos[10006][2];// 存储 输入的 数据
bool vis[10000007];// 标记 作用
int sett[30000];// 存储 所有的点 ， 用来 排序的
int temp[10000007];// 对数据进行离散化处理的数组bool cmp(const int a, const int b)
{return a < b;
}struct TreeNode
{int date;// 标记作用
}tree[8*10006]; // 最多有 2 * 10000 个 不同的 点 ，乘上 4 之后 可以保证有足够的空间建树void Build(int root, int s, int e)
{tree[root].date = 0;// 初始化 为 0 表示 没有标记if(s == e)return ;int mid = (s + e)/2;Build(root*2, s, mid);Build(root*2+1, mid+1, e);
}int Query(int root, int s, int e, int qs, int qe)
{if(tree[root].date == 1)// 表示 该区间 在后面 有海报 会将之覆盖 return 0;if(qs == s && e == qe){tree[root].date = 1;return 1;}int mid = (s + e)/2;int ans;if(qe <= mid)ans = Query(root*2, s, mid, qs, qe);else if(qs >= mid+1)ans = Query(root*2+1, mid+1, e, qs, qe);elseans = Query(root*2, s, mid, qs, mid) | Query(root*2+1, mid+1, e, mid+1, qe);// 左右区间 只要有一个 存在不被 覆盖 的 区间 就可以if(tree[root*2].date && tree[root*2+1].date)// 由左右子节点的状态 推出父节点的状态tree[root].date = 1;return ans;
}int main()
{int t; cin>>t;while(t--){scanf("%d", &n);memset(vis, false, sizeof(vis));// 下面是 离散化处理的过程 现存储 再去重排序 再数据更新为 离散化之后的数据int k = 0;for(int i = 0; i < n; i++){scanf("%d%d", &pos[i][0], &pos[i][1]);if(!vis[pos[i][0]])// 去重{sett[k++] = pos[i][0];vis[pos[i][0]] = true;}if(!vis[pos[i][1]])// 去重{sett[k++] = pos[i][1];vis[pos[i][1]] = true;}}sort(sett, sett+k, cmp);// 从小到大 排序for(int i = 0; i < k; i++)temp[sett[i]] = i + 1;// 将 数据离散化 seet【i】 =》i+1int sum = 0;Build(1, 1, k);// 因为离散化之后的数据的范围 为 1 =》 k for(int i = n-1; i >= 0; i--)// 逆序 输入数据{pos[i][0] = temp[pos[i][0]];pos[i][1] = temp[pos[i][1]];if(Query(1, 1, k, pos[i][0], pos[i][1]) > 0)sum++;}printf("%d\n", sum);}return 0;
}