| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 50643 | Accepted: 14675 |
Description
Input
Output
Sample Input
1 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
题意：一个城市要竞选市长，竞选者可以在一块墙上贴海报为自己拉票，每个人可以贴连续的一块区域，后来贴的可以覆盖前面的，问到最后一共可以看到多少张海报。
第一道离散化：（滚动数组优化） ORZ网上的大牛
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 10000+100
using namespace std;
struct Node
{
int x, y;
};
Node num[10100];
int color[MAXN<<4];
int rec[MAXN<<4];//离散化 存储
int Find(int val, int *a, int L, int R)//在a数组下标[L, R]范围里面 查找val值的下标
{
int left = L, right = R;
while(left <= right)
{
int mid = (left + right) >> 1;
if(a[mid] == val)
return mid;
if(a[mid] < val)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
void PushDown(int o)
{
if(color[o])
{
color[o<<1] = color[o<<1|1] = color[o];
color[o] = 0;
}
}
void update(int o, int l, int r, int L, int R, int v)
{
if(L <= l && R >= r)
{
color[o] = v;
return ;
}
PushDown(o);
int mid = (l + r) >> 1;
if(L <= mid)
update(o<<1, l, mid, L, R, v);
if(R > mid)
update(o<<1|1, mid+1, r, L, R, v);
}
int vis[10100];//标记该海报是否出现过
int ans;//纪录数目
void query(int o, int l, int r)
{
if(color[o])
{
if(!vis[color[o]])
ans++,vis[color[o]] = true;
return ;
}
//return ;
if(l == r)
return ;
int mid = (l + r) >> 1;
query(o<<1, l, mid);
query(o<<1|1, mid+1, r);
}
int main()
{
int t, N;
scanf("%d", &t);
while(t--)
{
scanf("%d", &N);
memset(color, 0, sizeof(color));
int len = 1;
for(int i = 1; i <= N; i++)
{
scanf("%d%d", &num[i].x, &num[i].y);
rec[len++] = num[i].x;
rec[len++] = num[i].y;
}
sort(rec+1, rec+len+1);
//离散化
int RR = 2;
for(int i = 2; i < len; i++)//滚动数组优化
{
if(rec[i] != rec[i-1])
rec[RR++] = rec[i];
}
for(int i = RR-1; i > 1; i--)
{
if(rec[i] != rec[i-1] + 1)
rec[RR++] = rec[i-1] + 1;
}
sort(rec+1, rec+RR);//不是RR+1
for(int i = 1; i <= N; i++)
{
int l = Find(num[i].x, rec, 1, RR-1);
int r = Find(num[i].y, rec, 1, RR-1);
update(1, 1, RR-1, l, r, i);
}
memset(vis, false, sizeof(vis));
ans = 0;
query(1, 1, RR-1);
printf("%d\n", ans);
}
return 0;
}版权声明：本文为博主原创文章，未经博主允许不得转载。
poj 2528 Mayor's posters 【线段树 + 离散化】
原文：http://blog.csdn.net/chenzhenyu123456/article/details/47811721