[题目|线段树]kuangbin-7-D（线段树+离散化）
题目描述
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.
They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters' size, their place and order of placement on the electoral wall.
输入格式
The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers l i and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= l i <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered l i, l i+1 ,... , ri.
输出格式
For each input data set print the number of visible posters after all the posters are placed.
The picture below illustrates the case of the sample input.
（假装这里有张图片，是一面被海报先后覆盖的墙）
输入样例#1
1
5
1 4
2 6
8 10
3 4
7 10
输出样例#1
4
思想
由本题加深了一点对线段树+离散化的理解，
本题有一个特点，因为是询问是否完全覆盖，故其查询区间需要“精确覆盖”所含区间，故而需要改写线段树中的规则。
1.首先需要使用&&来连接两部分st[o<<1]和st[(o<<1)|1]
2.之后看cmp的二级排序保证相邻的两个出自同一个segment
3.再次是需要保证st[o].l==ll&&st[o].r==rr，即精确相等
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
#include<iostream>
#include<map>
#define M 100005
using namespace std;
const int inf=0x7f7f7f7f;
struct point{
int x;
int id;
}a[M<<2];
struct tree{
int l;
int r;
bool vis;
}st[M<<2];
int flg;
bool cmp(point a,point b)
{
return a.x<b.x;
}
bool cmp2(point a,point b)
{
if(a.id==b.id) return a.x<b.x;
return a.id>b.id; //后覆盖的先取出使用
} //并且此种二级排序保证相邻的两个出自同一个segment
void build(int o,int ll,int rr)
{
st[o].l=ll;
st[o].r=rr;
st[o].vis=0;
if(st[o].l==st[o].r) return ;
int m=(ll+rr)>>1;
build(o<<1,ll,m);
build((o<<1)|1,m+1,rr);
}
void query(int o,int ll,int rr) //裁切询问区间，使其一层一层细分，直到精确等于（重要）某个vis==1的st段，并往回返
{
if(st[o].vis) return ;
if(st[o].l==ll&&st[o].r==rr) //此行if即为精髓，因为这类离散化的线段树并不具有传递性质，说白了，就是若一段区间若满足vis条件，但是其子区间并无vis条件的限制
{
st[o].vis=1;
flg=1;
return ;
}
int m=(st[o].l+st[o].r)>>1;
if(rr<=m) query(o<<1,ll,rr);
else if(ll>=m+1) query((o<<1)|1,ll,rr);
else //此else的作用是因为结束条件中均为精确等于号，若以上两if均不满足，则查询区间跨过了m中点，必裁切询问区间才可能精确等于
{
query(o<<1,ll,m);
query((o<<1)|1,m+1,rr);
}
st[o].vis=st[o<<1].vis&&st[(o<<1)|1].vis; //此结果已经在上层return之时由下层返上来了，并且用&&来确定是否整段区间均被覆盖
}
int main()
{
ios::sync_with_stdio(false);
int ll,rr;
int ans=0;
int c,n;
cin>>c;
while(c--)
{
// flg=0;
ans=0;
cin>>n;
for(int i=0;i<2*n;i+=2)
{
cin>>a[i].x;
cin>>a[i+1].x;
a[i].id=i;
a[i+1].id=i;
}
sort(a,a+2*n,cmp);
//离散化
int pre=0,tot=0;
/* for(int i=0;i<2*n;i++)
{
if(a[i].x!=pre)
{
a[i].x=++pre;
}
}*/
for(int i=0;i<2*n;i++)
{ //离散化，
if(a[i].x==pre)
a[i].x=tot;
else
{
pre=a[i].x;
a[i].x=++tot;
}
}
build(1,1,2*n);
/* for(int i=0;i<2*n;i++)
{
cout<<a[i].x<<" "<<a[i].id<<endl;
}*/
sort(a,a+2*n,cmp2);
for(int i=0;i<2*n;i+=2)
{
ll=a[i].x;
rr=a[i+1].x;
flg=0;
query(1,ll,rr);
if(flg)
ans++;
}
cout<<ans<<endl;
}
return 0;
}