Time Limit: 1000MS Memory Limit: 65536K
题目链接http://poj.org/problem?id=2528
Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.
They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.
Input
The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,… , ri.
Output
For each input data set print the number of visible posters after all the posters are placed.
The picture below illustrates the case of the sample input.
Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
题目大意：给每个区间贴纸，后面贴的会覆盖前面贴的，问最后能看到的纸有几张。
emmm，一种比较粗糙的算法就是直接用线段树暴力更新每一个区间，那么由于区间长度有1e7.。。。也就是说我们需要的线段树很大，需要一千万*4.。。。时间受不了，空间也受不了。。。但我们的想法是没什么问题的，只是我们需要优化时间和空间。
我们看看数据就会明显地发现只有一万个数据，最多19999个区间，我们根本用不了一千万这么大的数据，所以我们应该想办法将这些区间的数据进行压缩。我们将每一个区间的左右端点分别赋值，最多有2万个值，那么我们可以将之赋值为1-2万。
那么按照上述的方法来，我们将它所给的区间的左右端点的值排序，然后一一映射到1-2万上比如按样例来：
输入：
1,4
2,6
8,10
3,4
7,10
对端点排序（去重）：1,2,3,4,6,7,8,10
那么接下来我们将这些值重新映射到他们原本的位置就行了：
1,4
2,5
7,8
3,4
6,8
这五组数据就是经过压缩后的值，当l和r越大时，其压缩的程度也就越大。那么我们压缩完了就可以开心地线段树跑一遍啦。。。。
详细代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define blson rt*2,l,mid
#define brson rt*2+1,mid+1,r
#define lson rt*2,l,mid,col
#define rson rt*2+1,mid+1,r,col
#define debug printf ("**")
const int mac=1e4+10;
using namespace std;
struct node
{
int l,r,w;
}tree[mac*4];
struct node1
{
int pot,loca;
bool friend operator <(node1 a,node1 b){
return a.pot<b.pot;
}
}s[mac*4];
int map[mac*4][2],ans,v[mac*4];
void build(int rt,int l,int r);
void add(int rt,int l,int r,int col);
void ask(int rt);
int main()
{
int t,n,l,r;
scanf ("%d",&t);
while (t--){
scanf ("%d",&n);
for (int i=0; i<n; i++){//注意必须从0开始，不然s就会从2开始造成一些莫名的BUG
scanf ("%d%d",&map[i][0],&map[i][1]);
s[i*2].pot=map[i][0];
s[i*2+1].pot=map[i][1];
s[i*2].loca=-i-1;
s[i*2+1].loca=i+1;
}
sort(s,s+n*2);//printf ("\n");
int line=s[0].pot,cnt=1;
for (int i=0; i<2*n; i++){
if (line!=s[i].pot){
cnt++;
line=s[i].pot;
}
if (s[i].loca<0) map[-s[i].loca-1][0]=cnt;
else map[s[i].loca-1][1]=cnt;
}
build(1,1,cnt);
memset(v,0,sizeof(v));
for (int i=0; i<n; i++)
add(1,map[i][0],map[i][1],i+1);
ans=0;
ask(1);
printf ("%d\n",ans);
}
return 0;
}
void build(int rt,int l,int r)
{
tree[rt].l=l,tree[rt].r=r;
if (l==r){
tree[rt].w=0;
return;
}
int mid=(l+r)>>1;
build (blson);build (brson);
tree[rt].w=0;
}
void add(int rt,int l,int r,int col)
{
if (tree[rt].l==l && tree[rt].r==r){
tree[rt].w=col;//printf ("%d %d %d\n",tree[rt].w,tree[rt].l,tree[rt].r);
return;
}
int mid=(tree[rt].l+tree[rt].r)>>1;
if (tree[rt].w){//将颜色传给儿子
tree[rt*2].w=tree[rt*2+1].w=tree[rt].w;
tree[rt].w=0;
}
if (l>=tree[rt*2+1].l) add(rt*2+1,l,r,col);
else if (r<=tree[rt*2].r) add(rt*2,l,r,col);
else {//对满足的子区间向下染色
add(lson);add(rson);
}
}
void ask(int rt)
{
if (tree[rt].w){//该区间有颜色
if (!v[tree[rt].w]){
ans++;//printf ("%d ",ans);
v[tree[rt].w]=1;
}
return;
}
ask(rt*2);
ask(rt*2+1);
return;
}
几个月后回头练习线段树专题，然后发现这题之前写得跟坨shi一样QAQ。
以下是更新之后更清晰简洁的AC代码：注意这题的数据有问题，正规的离散化过不了，只有这种没有加隔板的离散化才能过。。。。
#include <cstdio>
#include <cstring>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
const int mac=2e4+10;
int tree[mac<<2],ans,vis[mac],b[mac];
struct node
{
int l,r;
}a[mac];
void build(int l,int r,int rt)
{
tree[rt]=0;
if (l==r) return;
int mid=(l+r)>>1;
build(lson);build(rson);
}
unordered_map<int,int>q;
void down(int rt)
{
tree[ls]=tree[rt];tree[rs]=tree[rt];
tree[rt]=0;
}
void update(int l,int r,int rt,int L,int R,int val)
{
if (l>=L && r<=R){
tree[rt]=val;
return;
}
if (tree[rt]) down(rt);
int mid=(l+r)>>1;
if (mid>=L) update(lson,L,R,val);
if (mid<R) update(rson,L,R,val);
}
void query(int l,int r,int rt)
{
if (l==r){
if (!vis[tree[rt]]) ans++;
vis[tree[rt]]=1;
return;
}
int mid=(l+r)>>1;
if (tree[rt]) down(rt);
query(lson);query(rson);
}
int main()
{
int t,n;
scanf ("%d",&t);
while(t--){
scanf ("%d",&n);
int cnt=0;
q.clear();
for (int i=1; i<=n; i++){
int l,r;
scanf ("%d%d",&l,&r);
a[i].l=l;a[i].r=r;
b[++cnt]=l;b[++cnt]=r;
}
sort(b+1,b+1+cnt);
int p=-1,use=1;
for (int i=1; i<=cnt; i++){
if (b[i]!=p) p=b[i],q[p]=use++;
}
use--;
build(1,use,1);
ans=0;
for (int i=0; i<=n; i++) vis[i]=0;
vis[0]=1;
for (int i=1; i<=n; i++) update(1,use,1,q[a[i].l],q[a[i].r],i);
query(1,use,1);
printf ("%d\n",ans);
}
return 0;
}