poj 2528 线段树离散化的小技巧

题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
思路:直接搞超时+超内存,需要离散化。
离散化简单的来说就是只取我们需要的值来
用,比如说区间[1000,2000],[1990,2012]
我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要
1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
而这题的难点在于每个数字其实表示的是一个单位长度(并且一个点),这样普通的离散化会造成许多错误
给出下面两个简单的例子应该能体现普通离散化的缺陷:
1-10 1-4 5-10
1-10 1-4 6-10
为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.

 #include<iostream>

 #include<string>

 #include<algorithm>

 #include<cstdlib>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<vector>

 #include<cstring>

 #include<stack>

 #include<cmath>

 #include<queue>

 #define clc(a,b) memset(a,b,sizeof(a))

 //#include <bits/stdc++.h>

 using namespace std;

 #define LL long long

 const int maxn=;

 int vis[maxn<<];

 int ans=;

 int x[maxn];

 int hashh[maxn<<];

 struct node

 {

     int l,r;

 } q[maxn];

 void pushdown(int rt)

 {

     if(vis[rt]!=-)

     {

         vis[rt<<]=vis[rt<<|]=vis[rt];

         vis[rt]=-;

     }

 }

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

 {

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

     {

         vis[rt]=c;

         return;

     }

     pushdown(rt);

     int m=(l+r)>>;

     if(L<=m) update(L,R,c,l,m,rt<<);

     if(R>m) update(L,R,c,m+,r,rt<<|);

 }

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

 {

     if(vis[rt]!=-)

     {

         if(!hashh[vis[rt]])

             ans++;

         hashh[vis[rt]]=;

         return;

     }

     if(l==r)

         return;

     int m=(l+r)>>;

     query(l,m,rt<<);

     query(m+,r,rt<<|);

 }

 int main()

 {

     int n,t;

     scanf("%d",&t);

     while(t--)

     {

         int cnt=;

         scanf("%d",&n);

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

         {

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

             x[cnt++]=q[i].l,x[cnt++]=q[i].r;

         }

         sort(x,x+cnt);

         int m=;

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

         {

             if(x[i]!=x[i-])

                 x[m++]=x[i];

         }

         for(int i=m-; i>=; i--)

             if(x[i]!=x[i-]+)

                 x[m++]=x[i-]+;

         sort(x,x+m);

         clc(vis,-);

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

         {

             int l=lower_bound(x,x+m,q[i].l)-x;

             int r=lower_bound(x,x+m,q[i].r)-x;

             update(l,r,i,,m,);

         }

         clc(hashh,);

         ans=;

         query(,m,);

         printf("%d\n",ans);

     }

     return ;

 }

巴特西

poj 2528 线段树离散化的小技巧

最新文章

热门文章

巴特西

poj 2528 线段树 离散化的小技巧

最新文章

热门文章

poj 2528 线段树离散化的小技巧