hiho一下第二十一周 #1079 : 离散化 【线段树储存区间状态】

#1079 : 离散化

10000ms

1000ms

256MB

描述

小Hi和小Ho在回国之后，重新过起了朝7晚5的学生生活，当然了，他们还是在一直学习着各种算法~

这天小Hi和小Ho所在的学校举办社团文化节，各大社团都在宣传栏上贴起了海报，但是贴来贴去，有些海报就会被其他社团的海报所遮挡住。看到这个场景，小Hi便产生了这样的一个疑问——最后到底能有几张海报还能被看见呢？

于是小Ho肩负起了解决这个问题的责任：因为宣传栏和海报的高度都是一样的，所以宣传栏可以被视作长度为L的一段区间，且有N张海报按照顺序依次贴在了宣传栏上，其中第i张海报贴住的范围可以用一段区间[a_i, b_i]表示，其中a_i, b_i均为属于[0, L]的整数，而一张海报能被看到当且仅当存在长度大于0的一部分没有被后来贴的海报所遮挡住。那么问题就来了：究竟有几张海报能被看到呢？

​​提示一：正确的认识信息量​​

​​提示二：小Hi大讲堂之线段树的节点意义​​

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第1行为两个整数N和L，分别表示总共贴上的海报数量和宣传栏的宽度。

每组测试数据的第2-N+1行，按照贴上去的先后顺序，每行描述一张海报，其中第i+1行为两个整数a_i, b_i，表示第i张海报所贴的区间为[a_i, b_i]。

对于100%的数据，满足N<=10^5，L<=10^9，0<=a_i<b_i<=L。

输出

对于每组测试数据，输出一个整数Ans，表示总共有多少张海报能被看到。

样例输入

5 10

4 10

0 2

1 6

5 9

3 4

样例输出

5

提示一：正确的认识信息量

小Ho听完小Hi的描述，不屑道：“这不就是一个很简单的线段树问题么，每一张海报其实就是一次修改，在线段树上利用​​懒惰标记​​进行维护——“每个节点对应的区间上是否只有一张海报？如果有，是哪一张？”，然后在全部海报处理完成之后，扫描一遍整个线段树，看仍然‘存活’的海报有哪些，就可以知道答案了！”

“对，你说的很有道理！”小Hi点头表示赞同，又随即问道：“但是你这棵线段树有多大呢？”

“不就是O(N)大小的么……额，应该是O(L)大小的……因为叶子节点个数是L个，那么这个树的空间开出来，似乎内存要炸啊。”小Ho意识到了问题所在。

“那你准备如何处理？”小Hi问道。

“等等，我觉得很不科学啊……你想想，这个问题最关键的问题在于这N个区间之间的相互覆盖关系，而和这N个区间所处的‘舞台’也就是这个宣传栏没有什么关系，那么为什么解决这个问题的复杂度反倒会和舞台的宽度L有关呢？。”小Ho不解道。

小Hi点头道：“对，这就是关键问题，[1, 1000000]、[2, 1000001]这两个区间在这个问题中和[1, 3]、[2, 4]两个区间其实并没有什么不同，但是为了维护前一种情况所需要的线段树就是非常巨大的。”

小Ho沉思半刻，道：“那么我所需要解决的问题，就是将[1, 1000000]、[2, 1000001]这样的区间转化成和它等价的[1, 3]、[2, 4]这样的区间咯？唔……但是想要弄清楚N个区间之间的关系话，是很复杂的，更何况如果我在弄清楚这N个区间关系的过程中，想必这个题目的问题就已经得到解决了吧？”

小Hi笑道：“所以说你走了弯路，太着相于区间这个东西上面了。”

小Ho表示理解不能。

小Hi便继续道：“在这个问题的计算过程中，对于这些区间来说，其实并不会在乎具体数值是多少，而是在他们的左右端点之间互相进行比较而已。所以你就把这N个区间的左右端点——2N个整数提出来，处理一下呗？你要注意的是，这2N个数是什么其实并不重要，你可以把这2N个数替换成为任何另外2N个数，只要他们之间的相对大小关系不发生改变就可以。”

小Ho点了点头，想道：“这2N个数……在数轴上就是最多2N个点，如果我把其中数值最小的点命名为第1个点，简称‘1’，数值次小的点命名为第2个点，简称‘2’……依次类推，那么这些点最多就命名到第2N个点。也就是说他们的数值范围缩小到了O(N)级别，但是这2N个数的相对大小关系并没有发生改变。比如说[1, 1000000]、[2, 1000001]、[2, 10]这3个区间的左右端点组成的集合为{1, 2, 10, 1000000, 1000001}，那么我就将这个集合对应到{1, 2, 3, 4, 5}，那么原来的三个区间就变成了[1, 4]、[2, 5]、[2, 3]这3个区间，但是他们的相互覆盖关系却是一点变化都没有！”

小Ho又思考一番，觉得没有什么问题，于是道：“那么我需要额外做的事情就是在构建线段树之前对区间进行预处理：将区间的左右端点选出来，组成一个集合，然后将这个集合依次对应到正整数集合上，并且利用这个对应将原来的区间的左右端点更换为新的值。这样新构建的区间在这个问题中的答案和原来区间是一样的，但是新区间的范围就是O(N)这个级别的，我就可以用O(N)的时间复杂度和空间复杂度构建出线段树了！”

“是的呢！但是你要不要手动写一下尝试一下？离散化——将连续的区间转化成为离散的点在编写的过程中可还是有很多小问题的哦！”

提示二：小Hi大讲堂之线段树的节点意义

在线段树的通常用法中，线段树的节点是有2种不同的意义的，一种是离散型的，比如在​​Hiho一下 第二十周​​中，一个节点虽然描述的是一个区间[3, 9]，但是实际上这样一个区间是{3, 4, 5, 6, 7, 8, 9}这样的意义。而另一种就是连续型的，比如就在这一周的问题中，一个节点如果描述的是一个区间[3, 9]，它就确确实实描述的是在数轴上从3这个标记到9这个标记的这一段。

那么有的小朋友可能就要问了，这两种不同的意义有什么区别呢？

在小Hi看来，其实只有这样的几个区别：1.叶子节点：在离散型中，叶子节点是[i, i]，而连续性中是[i, i + 1]；2.分解区间：在离散型中，一段区间是分解成为[l, m], [m + 1, r]，而在连续型中，是分解成为[l, m], [m, r]；3.其他所有类似的判定问题。

那么亲爱的小朋友们，你们懂了么？

和上次的线段树有一点区别-.-这次储存的是区间-.-所以二分线段树时分为了[L , M ]  和  [M , R ]。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,zuo[100100],you[100100];
bool she[300000];
struct node{
    int hao,shu;
}yy[200200];
struct node1{
    int hao,shu;
}yyy[200200];
struct nn{
    int l,r,lei;
    bool fafe;
}trie[300000];
bool cmp(node xx,node yy)
{
    return xx.shu<yy.shu;
}
void in(int x,int y)
{
    if (x<m)
        zuo[x]=y;
    else
        you[x-m]=y;
    return ;
}
void sss()
{
    int lp=1;
    in(yy[0].hao,lp);
    for (int i=1;i<2*m;i++)
    {
        if (yy[i].shu!=yy[i-1].shu)
            lp++;
        in(yy[i].hao,lp);
    }
    n=lp;
}
void update(int x)
{
    if (trie[x*2].fafe&&trie[x*2+1].fafe&&trie[x*2].lei==trie[x*2+1].lei)
    {
        trie[x].fafe=true;
        trie[x].lei=trie[x*2].lei;
    }
    else
        trie[x].fafe=false;
}
void build_trie(int l,int r,int x)
{
    trie[x].l=l;trie[x].r=r;
    trie[x].fafe=false;
    if (r-l==1)
    {
        trie[x].fafe=true;
        trie[x].lei=0;
        return ;
    }
    int m=(l+r)>>1;
    build_trie(l,m,x*2);
    build_trie(m,r,x*2+1);
    update(x);
}
void query(int l,int r,int se,int x)
{
    if (l==trie[x].l&&r==trie[x].r)
    {
        trie[x].fafe=true;
        trie[x].lei=se;
        return ;
    }
    int m=(trie[x].l+trie[x].r)>>1;
    if (trie[x].fafe)
    {
        trie[x*2].fafe=true;
        trie[x*2].lei=trie[x].lei;
        trie[x*2+1].fafe=true;
        trie[x*2+1].lei=trie[x].lei;
    }
    if (r<=m)
        query(l,r,se,x*2);
    else if (l>=m)
        query(l,r,se,x*2+1);
    else
    {
        query(l,m,se,x*2);
        query(m,r,se,x*2+1);
    }
    update(x);
}
void solve(int x)
{
    if (trie[x].r-trie[x].l==1)
    {
        she[trie[x].lei]=true;
        return ;
    }
    if (trie[x].fafe)
    {
        trie[x*2].fafe=true;
        trie[x*2].lei=trie[x].lei;
        trie[x*2+1].fafe=true;
        trie[x*2+1].lei=trie[x].lei;
    }
    {
        solve(x*2);
        solve(x*2+1);
    }
}
int main()
{
    scanf("%d%d",&m,&n);
    for (int i=0;i<m;i++)
    {
        scanf("%d%d",&zuo[i],&you[i]);
        yy[i].shu=zuo[i];
        yy[i].hao=i;
        yy[i+m].shu=you[i];
        yy[i+m].hao=i+m;
    }
    sort(yy,yy+2*m,cmp);
    sss();
    build_trie(1,n,1);
    for (int i=0;i<m;i++)
    {
        query(zuo[i],you[i],i+1,1);
    }
    memset(she,false,sizeof(she));
    solve(1);
    int ans=0;
    for (int i=1;i<=m;i++)
        if (she[i])
            ans++;
    printf("%d\n",ans);
    return 0;
}