【线段树+离散化】POJ2528-Mayor's posters

【题目大意】

在墙上贴海报，问最后能看到几张海报？

【注意点】

1.首先要注意这是段线段树，而非点线段树。读题的时候注意观察图。来看discuss区下面这组数据：

5 6

4 5

6 8

上面数据的答案应该是2，注意观察图，覆盖的是区间。

2.离散化

由于覆盖的是区间，不能简单的离散化，否则会出现差错。比如说下面这组数据：

1 5

1 3

4 5

以及

1 5

1 2

4 5

如果简单离散化都会变成：

1 4

1 2

3 4

最后得出只能看到两张海报的结论，而事实上第一组数据中能够看到三张海报，为了解决这个问题，如果相邻两个数之间相差大于1，就补上一个中间的数字。

比如说1 4，离散化成为1 2 3

3.数据范围：线段树要开到<<4，至于为什么还没有研究出来。X要开到三倍，因为不仅要考虑左右边界均放进来，而且还要考虑中间增添上来离散化的数字。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 /*define后面绝对不能加分号*/

 using namespace std;

 const int MAXN=+;

 int l[MAXN],r[MAXN];

 int X[MAXN*],t,M;

 int col[MAXN<<];

 int hash[MAXN];

 /*延迟标记当前区域被编号为几的覆盖*/

 int ans;

 void pushdown(int rt)

 {

     if (col[rt]!=-)

     {

         col[rt<<]=col[rt];

         col[rt<<|]=col[rt];

         col[rt]=-;

     }

 }

 int Bin(int key)

 {

     int ub=,lb=M+;

     while (lb>ub)

     {

         int m=(ub+lb)/;

         if (X[m]==key) return m;

         if (X[m]>key) lb=m;

             else (ub=m);

     }

     return -;

 }

 void update(int L,int R,int l,int r,int rt,int cit)

 {

     if (L<=l && r<=R)

     {

         col[rt]=cit;

         return;

     }

     pushdown(rt);

     int m=(l+r)>>;

     if (L <= m) update(L,R,lson,cit);

     if (m < R) update(L,R,rson,cit);

 }

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

 {

     if (col[rt]!=-)

     {

         if (hash[col[rt]]!=) ans++;

         hash[col[rt]]=;

         return;

     }

     if (l==r) return;

     int m=(l+r)>>;

     query(lson);

     query(rson);

 }

 void init()

 /*输入数据并进行离散化*/

 {

     int num=;

     scanf("%d",&t);

     for (int i=;i<t;i++)

     {

         scanf("%d%d",&l[i],&r[i]);

         X[++num]=l[i];

         X[++num]=r[i];

     }

     sort(X+,X+num+);

     /*M来记录离散化之后总共出现了几个数字*/

     M=;

     /*注意因为下面的for循环是从2开始的，所以m的初始值要是1，否则第一个数字会被覆盖掉*/

     for (int i=;i<=num;i++)

     {

         if (X[i]!=X[i-]) X[++M]=X[i];

         /*重复的数字只记录一次*/

     }

     num=M;

     for (int i=;i<=num;i++)

     {

         if (X[i]-X[i-]>) X[++M]=X[i]-;

         /*离散化时要注意，如果两个点相差大于1，则在中间再插入一个数字*/

     }

     sort(X+,X+M+);

 }

 void submain()

 {

     memset(col,-,sizeof(col));

     for (int i=;i<t;i++)

     {

         int lp=Bin(l[i]);

         int rp=Bin(r[i]);

         update(lp,rp,,M,,i);

         /*二分查找左边界和右边界离散化后对应的数值*/

     }

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     for (int kase=;kase<T;kase++)

     {

         init();

         submain();

         ans=;

         memset(hash,,sizeof(hash));

         query(,M,);

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

【线段树+离散化】POJ2528-Mayor's posters

最新文章

热门文章