先讲一下：dalao @lisuier 发布的前一篇题解严格来讲是有错误的

比如下一组数据：

1

3

1 10

1 4

7 10

显然答案是3，然而用lisuier dalao的程序做出来的答案是2（后面会讲错误原因）

简单看出这道题用线段树可解

so

我们用离散化+权值线段树（戳这里详解）

实际上是安利自己博客

思路：建一棵空数，然后把某一区间的颜色更新为读入的颜色；

WA,SO EASY

OK

那我们先建一棵(10^7*4)的空树

然后

空间就炸了

正经的处理方法

对区间端点进行离散化

接下来

引用一下的 @lisuier 的话

离散化，如下面的例子，因为单位1是一个单位长度，将下面的

1 2 3 4 6 7 8 10

— — — — — — — —

1 2 3 4 5 6 7 8

离散化 X[1] = 1; X[2] = 2; X[3] = 3; X[4] = 4; X[5] = 6; X[7] =8; X[8] = 10

这样我们就优化了空间

对一般的离散化来说，这很对，

但是

再看这一组数据

用该方法离散化后

第二张海报与第三张海报中间的间隔就消...消失了

也就是说第一张海报就看不到了（手动模拟一下发现是能看到的）

处理方法：离散化时，加到临时数组b中的右端点+1也加到临时数组中

看起来是这样的

int init(){//读入并进行离散处理

    n = read(); tot=0;

    for(int i = 1;i <= n;i++)

        a[i].l = read(),a[i].r = read(),

        b[++tot] = a[i].l,b[++tot] = a[i].r,b[++tot] = a[i].r + 1;//加入右边的端点+1

    sort(b + 1,b + tot + 1);

    int len=unique(b + 1,b + tot + 1) - b - 1;

    for(int i = 1; i <= n;i++)

        a[i].l = lower_bound(b + 1,b + len + 1,a[i].l) - b,

        a[i].r = lower_bound(b + 1,b + len + 1,a[i].r) - b; //下面是正常的离散化

    return len; //离散化后总共处理多长的墙;

}

更新之类的与普通线段树差不多

但是要注意push_down操作和query操作

比如说询问时已经访问过得颜色要标记一下

接下来是

简单易懂

的代码.

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define M 20005

using namespace std;

inline int read(){

    char chr=getchar(); int f=1,ans=0;

    while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}

    while(isdigit(chr))  {ans=ans*10;ans+=chr-'0';chr=getchar();}

    return ans*f;

}

int ans = 0;

struct segment

{

int l,r;

}a[10005 << 4];

bool vis[20005 << 4];

struct node

{

    int l,r,val,lazy,sum;

    int mid()

    {

        return l + r >> 1;

    }

}t[M << 4];

int b[20005 << 4],n,tot=0,x,y;

int init()

{//读入并进行离散处理

    n = read();

    tot = 0;

    for(int i = 1;i <= n;i++)

        a[i].l = read(),

        a[i].r = read(),

        b[++tot] = a[i].l,

        b[++tot] = a[i].r,

        b[++tot] = a[i].r + 1;

    sort(b + 1,b + tot + 1);

    int len=unique(b + 1,b + tot + 1) - b - 1;

    for(int i = 1; i <= n;i++)

        a[i].l = lower_bound(b + 1,b + len + 1,a[i].l) - b,

        a[i].r = lower_bound(b + 1,b + len + 1,a[i].r) - b;

    return len; //离散化后总共处理多长的墙;

}

void push_down(int i){

    if(t[i].val == -1)  return;

    t[i << 1].val = t[i << 1 | 1].val = t[i].val;

    t[i].val = -1;

}

void build(int i,int l,int r)

{

    t[i].l = l;

    t[i].r = r;

    t[i].val = 0;

    if(l == r)

    {

        return;

    }

    int m=t[i].mid();

    build(i << 1,l,m);

    build(i << 1 | 1,m + 1,r);

}

void updata(int i,int l,int r,int x)

{

    if(l <= t[i].l && t[i].r <= r)

    {

        t[i].val = x;

        return;

    }

    push_down(i);

    int m = t[i].mid();

    if(l <= m)

        updata(i << 1,l,r,x);

    if(r > m)

        updata(i << 1 | 1,l,r,x);

}

void query(int i,int l,int r)

{

    if(t[i].val != -1)

    {

    	 if(!vis[t[i].val])

         {

            vis[t[i].val] = 1;//做标记

            ++ans;

         }

        return;

    }

    query(i << 1,l,r);

    query(i << 1 | 1,l,r);

}

int ask(int l,int r)

{

    memset(vis,0,sizeof(vis));

    ans = 0;

    vis[0] = 1;

    query(1,l,r);

    return ans;

}

int main()

{

    int T = read();

    while(T--)

    {

        int m=init();   tot=0;//海报染成的颜色

        build(1,1,m);

        for(int i = 1;i <= n;i++)

            updata(1,a[i].l,a[i].r,++tot);

        printf("%d\n",ask(1,m));

    }

    return 0;

}

巴特西

题解 UVA10587 【Mayor's posters】