市长海报/ Mayor‘s posters
AB 省 Bytetown 的市民无法忍受市长竞选活动的候选人随心所欲地将他们的选举海报贴在各个地方。市议会最终决定建造一面选举墙来放置海报，并引入以下规则：
他们建造了一堵 10000000 字节长的墙（这样就有足够的空间容纳所有候选人）。当竞选活动重新开始时，候选人将他们的海报贴在墙上，他们的海报宽度差异很大。此外，候选人开始将他们的海报张贴在已经被其他海报占据的墙面上。Bytetown 的每个人都很好奇，在选举前的最后一天，谁的海报将（全部或部分）可见。
您的任务是根据海报的大小、位置和在选举墙上的放置顺序等信息，找出放置所有海报时可见海报的数量。
- 每个候选人都可以在墙上放置一张海报。
- 所有海报的高度都与墙壁的高度相同;海报的宽度可以是任意整数字节（byte 是 Bytetown 中的长度单位）。
- 墙被分成几段，每段的宽度为 1 个字节。
- 每张海报必须完全覆盖连续数量的墙段。
他们建造了一堵 10000000 字节长的墙（这样就有足够的空间容纳所有候选人）。当竞选活动重新开始时，候选人将他们的海报贴在墙上，他们的海报宽度差异很大。此外，候选人开始将他们的海报张贴在已经被其他海报占据的墙面上。Bytetown 的每个人都很好奇，在选举前的最后一天，谁的海报将（全部或部分）可见。
您的任务是根据海报的大小、位置和在选举墙上的放置顺序等信息，找出放置所有海报时可见海报的数量。
输入
输入的第一行包含一个数字 c，给出后面的 case 数。单个案例的第一行数据包含数字 1 <= n <= 10000。随后的 n 行按海报的放置顺序描述海报。n 行中的第 i 行包含两个整数 li 和 ri，分别是第 i 张海报的左端和右端所占据的墙段编号。我们知道，对于每个 1 <= i <= n， 1 <= li <= ri <= 10000000。放置第 i 张海报后，它将完全覆盖编号为 li、li+1 ,... , ri 的所有墙段。
输出
对于每个输入数据集，在放置所有海报后打印可见海报的数量。
下图说明了 sample input 的情况。
下图说明了 sample input 的情况。
样本
| 输入复制 | 输出复制 |
|---|---|
1
5
1 4
2 6
8 10
3 4
7 10
| 4 |
思路：
因为范围比较大，所以用离散化将其范围变小，然后在用线段树做题
代码：
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct sss {
int x, y, k;
}a[80005];//线段树
bool b[10005];//判断海报是否访问过
struct ss {
int x, i;//i 第i个坐标
bool v;//判断是左边还是右边边界
}c[20005],e[20005];//归并离散化，减少范围
struct s{
int x, y;
}d[10005];//离散化后的墙段
int f, n, x, y;
//建立线段树
void bulid(int i,int x, int y) {
a[i].x = x;
a[i].y = y;
a[i].k = 0;
if (x == y) {
return;
}
int mid = (x + y) / 2;
bulid(2 * i, x, mid);
bulid(2 * i + 1, mid + 1, y);
}
//线段树的区间修改
void tianjia(int i, int x, int y, int j) {
if (a[i].x >= x && a[i].y <= y) {
a[i].k = j;
return;
}
else if((a[i].x < x && a[i].y >=x)||(a[i].x <=y && a[i].y > y)){
if (a[i].x == a[i].y) {
return;
}
if (a[i].k != 0) {
a[i * 2 + 1].k = a[i].k;
a[i * 2].k = a[i].k;
a[i].k = 0;
}
int mid = (a[i].x + a[i].y) / 2;
if (mid >= x)
tianjia(2 * i, x, y, j);
if (mid < y)
tianjia(2 * i + 1, x, y, j);
}
else {
return;
}
}
//清除痕迹
void qingchu(int i) {
a[i].k = 0;
if(a[i].x!=a[i].y)
{
qingchu(i * 2);
qingchu(i * 2 + 1);
}
}
//查询多少海报漏出来
void chazhao(int i,int &q) {
if (a[i].k != 0) {
if(b[a[i].k] == false){
q++;
b[a[i].k] = true;
}
qingchu( i);
return;
}
else if (a[i].x == a[i].y) {
return;
}
else {
chazhao(i * 2, q);
chazhao(i * 2 + 1, q);
}
}
//归并排序
void guibing(int i, int j) {
if (i >= j) {
return;
}
int mid = i + (j - i) / 2;
guibing(i, mid);
guibing(mid + 1, j);
int r = i, l = mid + 1, h = i;
while (r <= mid && l <= j) {
if (c[r].x < c[l].x) {
e[h] = c[r];
h++;
r++;
}
else {
e[h] = c[l];
h++;
l++;
}
}
while (r <= mid) {
e[h]= c[r];
h++;
r++;
}
while (l <= j) {
e[h] = c[l];
h++;
l++;
}
h = i;
while (h <= j) {
c[h] = e[h];
h++;
}
}
int main(){
scanf("%d", &f);
bulid(1, 1, 20000);
while (f--) {
scanf("%d", &n);
for(int i=1;i<=n;i++){
scanf("%d %d", &c[i].x, &c[n+i].x);
c[i].i = i, c[i].v = true;
c[i + n].i = i; c[i+n].v = false;
}//记录，方便后序离散化
guibing(1, 2 * n);
int j = 1;
for (int i = 1; i <= 2 * n; i++) {
if (c[i].x != c[j].x)
j=i;//使相同的数离散化后相同
if (c[i].v == true)
d[c[i].i].x = j;
else
d[c[i].i].y = j;
}
//区间修改
for (int i = 1; i <= n; i++) {
tianjia(1, d[i].x, d[i].y, i);
}
//查找记录
int q = 0;
chazhao(1, q);
printf("%d\n", q);
//清除标记
memset(b, false, (n+1)*sizeof(bool));
}
return 0;
}