poj2528（离散化+线段树）

题意：在1-10^7的长度上贴海报，求能看到的海报数目

解题思路:10^7无论用朴素法或线段树解都会超时超内存，所以要进行离散化。所谓离散化就是把有限的个体映射到有限的空间，以此提高算法的时空效率以这题的测试数据为例，本题的五个区间为1 4，2 6，8 10，3 4，7 10；其中10和4出现了两次，把重复的数字去除，然后排序得1 ，2,3,4,6,7,8,10,与之对应的数组下标为1 2 3 4 5 6 7 8，以数组下标区间边界得到新的五个区间为[1,4],[2,5],[7,8],[3,4],[6,8].有题目知每次区间最多给10000个，那么线段树的N = 20000.接下来就用线段树的成段更新就可以了，这里不用信息的维护

离散化的一些注意事项：
1、有n个数字ai，n一般小于10^6 ，而这些数字的范围却很大，比如 0 <= ai <= 1,000,000,000 , 先在按我们的思路要把ai当做下标
这时候要用离散化
2、ai 中没有相同的数字
如poj2299和poj2528

代码如下：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<time.h>
#include<math.h>
#define N 20000 + 5
#define inf 0x7fffffff
#define eps 1e-9
#define pi acos(-1.0)
#define P system("pause")
using namespace std;
int tree[N*4], mapp[N][2];
int x,y;
set<int> q;
struct node
{
int val,bor;
}s[2*N];
bool cmp (node a,node b)
{
return a.val < b.val;
}
void pushdown(int o)
{
if(tree[o] > 0)
{
tree[2*o] = tree[2*o+1] = tree[o];
tree[o] = -1;
}
}
void update(int o,int l,int r,int k)
{
if(x <= l && y >= r)
{
tree[o] = k;
}
else
{
int m = (l+r)/2;
pushdown(o);
if(x <= m) update(2*o,l,m,k);
if(y > m) update(2*o+1,m+1,r,k);
}
}
void query(int o,int l,int r)
{
if(tree[o] > 0) {
q.insert(tree[o]);
return;
}
if(l == r) return;
int m = (l+r)/2;
query(2*o,l,m);
query(2*o+1,m+1,r);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
memset(tree,-1,sizeof(tree));
int i;
for(i = 0; i < n ; i++)
//离散化
{
scanf("%d%d",&mapp[i][0],&mapp[i][1]);
s[2*i].val = mapp[i][0];
s[2*i+1].val = mapp[i][1];
s[2*i].bor = -(i+1);
s[2*i+1].bor = i+1;
}
sort(s,s+2*n,cmp);
int k = 1;
if(s[0].bor < 0)
mapp[-s[0].bor-1][0] = k;
else
mapp[s[0].bor-1][1] = k;
for(i = 1; i < 2*n; i++)
{
if(s[i].val != s[i-1].val)
k++;
if(s[i].bor < 0)
mapp[-s[i].bor-1][0] = k;
else
mapp[s[i].bor-1][1] = k;
}
// for(i = 0; i < n; i++)
//
cout<<mapp[i][0]<<" "<<mapp[i][1]<<endl;
for(i = 0; i < n; i++)//线段树成段更新
{
x = mapp[i][0];
y = mapp[i][1];
update(1, 1, k, i+1);
}
q.clear();
query(1,1,k);
printf("%dn",q.size());
}
return 0;
}
/*
1
5
1 4
2 6
8 10
3 4
7 10
*/

最后

以上就是热情百褶裙为你收集整理的poj2528（离散化+线段树）的全部内容，希望文章能够帮你解决poj2528（离散化+线段树）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。