Photo by Kellie Churchman from Pexels
题意说的是，有一面非常非常长的墙，现在要向这面墙上贴上若干张宽度不等的海报，问贴完后有多少张海报能看得到(也就是有多少张海报没有被完全覆盖)。
抽象一下问题就是，有一段无限长的线段，现在要对线段上的某一段染色，问经过若干次染色后，线段上一共有多少种颜色。
因为涉及到了区间修改(贴海报),所以很自然想到用线段树去维护。一开始我的想法是写个线段树去维护墙壁上的海报，“贴海报”对应将某个区间上的值设置为当前要贴的海报对应的id，然后再搞个查询区间和的操作，通过区间和来判断当前要贴的海报的状态(一共三种状态：1.完全不会覆盖当前区间已经存在的海报，此时对应区间和为0；2.会部分覆盖当前区间已经存在的海报；3.会完全覆盖当前区间已经存在的海报)......但这样做其实很不好实现，最明显的问题就是要怎么判断会完全覆盖这种情况？还有就是如果当前区间存在不止一张海报，那又怎么搞？
然后后来发现完全不用这么麻烦OTZ，直接搞个set操作(将当前区间的值设为某一个特定的id)，然后query的时候看一下当前区间有没有被贴海报，同时如果有被贴海报的话，海报对应的id是否已经被访问过了(这里要另外用个vis数组维护一下)，同时满足上面这两个条件的话，就说明有一张海报能被看见，所以ans++......
然后还有就是要做一下离散化，因为本题数据范围很大，直接搞的话感觉是要MLE的。这里再简单说一下离散化，毕竟这是蒟蒻第二次做有关离散化的题OTZ，就当作是一个笔记。
所谓的离散化，就是将一个范围很大的数，转化为数据范围更小的数，从而大大减少内存使用。使用离散化的其中一个场景是，有时候序列中的数的范围很大，且不是连续的，但我们只关心这些数字之间的相对大小，不关心它们的具体数值。这时就可以使用离散化处理，将它们映射到一组连续且数据范围小得多的数字上。离散化的大致步骤是
- 排序，这是为了后面的去重和二分
- 去重，这里使用的是C++的unique()函数。这个函数的功能是对于一段连续的数，只保留它们中的第一个，比方说2，2，2，4，5，6，2，使用unique()后，会变成2，4，5，6，2，最后一个2因为不是连续的，所以不会被删除。因此，在使用unique()去重时，必须要保证序列是有序的，这个用sort()处理一下即可
- 去重完毕后，使用lower_bound将原序列中的数映射到一个更小的数字上。
以这道题的样例为例子： 1 4 2 6 8 10 3 4 7 10 这是五张海报的左右端点。我们首先对它们进行排序和去重。处理后可以得到这样的一个序列：
我们现在将这些只进行映射，具体来说就是：
| 原数值 | 映射值 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 6 | 5 |
| 7 | 6 |
| 8 | 7 |
| 10 | 8 |
关于映射，再举一个例子：对于序列1、1000、100000000，我们可以将他们映射到1、2、3上，这样一来，就能将数据范围大大减小。
看了下题解，发现这道题不能这么简单的离散化，但这题的数据比较弱，所以依然能AC...emmmm，蒟蒻不懂OTZ
具体AC代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cctype>
#include <string>
#include <queue>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=10005;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int vis[10000+5];
int lazy[maxn<<3]; //这里最好开大一点，仅仅是四倍空间的话会WA
struct node{
int lef;
int rig;
};
node ps[20000+5];
void pushdown(int rt)
{
if(lazy[rt]!=0){
lazy[rt<<1]=lazy[rt<<1|1]=lazy[rt];
lazy[rt]=0;
}
return ;
}
int ans=0;
void update(int toL,int toR,int todo,int lef,int rig,int rt)
{
if(toL<=lef&&toR>=rig){
lazy[rt]=todo;
return ;
}
pushdown(rt);
int mid=lef+(rig-lef)/2;
if(toL<=mid)
update(toL,toR,todo,lson);
if(toR>mid)
update(toL,toR,todo,rson);
return ;
}
void query(int lef,int rig,int rt)
{
if(lazy[rt]){
if(!vis[lazy[rt]]){
ans++;
vis[lazy[rt]]=1; //防止同一张海报重复统计
}
return ;
}
if(lef==rig)
return ;
pushdown(rt);
int mid=lef+(rig-lef)/2;
if(lef<=mid)
query(lson);
if(rig>mid)
query(rson);
}
int lsh[maxn<<2];
int main()
{
int t;
cin>>t;
while(t--){
int idx=0;
mst(lsh,0);
mst(lazy,0);mst(vis,0);
ans=0;
int n;cin>>n;
for(int i=0;i<n;i++){
scanf("%d %d",&ps[i].lef,&ps[i].rig);
lsh[idx++]=ps[i].lef;lsh[idx++]=ps[i].rig;
}
sort(lsh,lsh+idx);
int cnt=unique(lsh,lsh+idx)-lsh;
for(int i=0;i<n;i++){
int L=lower_bound(lsh,lsh+cnt,ps[i].lef)-lsh+1;
int R=lower_bound(lsh,lsh+cnt,ps[i].rig)-lsh+1;
update(L,R,i+1,1,cnt+1,1);
}
query(1,cnt+1,1);
printf("%d\n",ans);
}
return 0;
}