| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 45031 | Accepted: 13080 |
Description
Input
Output
Sample Input
1 5 1 4 2 6 8 10 3 4 7 10
Sample Output
4
这道题也做了好久。首先，每个数可以代表一个格子，求最后没有被覆盖的格子数，同一段区间的格子算一个。把区间离散化，但有一个问题，会导致错误。
如[1,10]、[1 4]、[6 10],离散化后是{1,4,6,10}对应下表是{0,1,2,3} ，区间变为[0,3][0,1][2,3],第一段区间被完全覆盖了，但原区间中第一段不会完全覆盖。所以，可以在相邻两个差值大于1的数中间添加一个数，使它们不会出错。
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<stdlib.h>
#include<vector>
#include<algorithm>
using namespace std;
#define N 10005
#define ll long long
struct node
{
int x,id;
}a[N*4]; //2*n个端点+（2*n-1）
int pos[N][2],ans;
struct st
{
int l,r,x; //x记录颜色，初始化-1
}f[N*20];
int mark[N*4];
bool cmp(node a,node b)
{
return a.x<b.x;
}
void creat(int t,int l,int r)
{
f[t].l=l;
f[t].r=r;
f[t].x=-1;
if(l==r)
return ;
int tmp=t<<1,mid=(l+r)>>1;
creat(tmp,l,mid);
creat(tmp|1,mid+1,r);
}
void update(int t,int l,int r,int x)
{
if(l==f[t].l&&r==f[t].r)
{
f[t].x=x;
return ;
}
int tmp=t<<1,mid=(f[t].l+f[t].r)>>1;
if(f[t].x!=-1)
{
f[tmp].x=f[tmp|1].x=f[t].x;
f[t].x=-1;
}
if(mid>=r)
update(tmp,l,r,x);
else if(l>mid)
update(tmp|1,l,r,x);
else
{
update(tmp,l,mid,x);
update(tmp|1,mid+1,r,x);
}
}
void query(int t,int l,int r)
{
int tmp=t<<1,mid=(f[t].l+f[t].r)>>1;
if(l==r)
{
if(!mark[f[t].x]&&f[t].x!=-1) //此处注意
{
mark[f[t].x]=1;
ans++;
}
return ;
}
if(f[t].x!=-1)
{
f[tmp].x=f[tmp|1].x=f[t].x;
f[t].x=-1;
}
if(r<=mid)
query(tmp,l,r);
else if(l>mid)
query(tmp|1,l,r);
else
{
query(tmp,l,mid);
query(tmp|1,mid+1,r);
}
}
int main()
{
int i,T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d%d",&pos[i][0],&pos[i][1]);//左右边界
a[i*2].x=pos[i][0];
a[i*2].id=-(i+1);
a[i*2+1].x=pos[i][1];
a[i*2+1].id=i+1;
}
sort(a,a+n*2,cmp);
int m=n*2;
for(i=m-1;i>0;i--) //添加数字，
{
if(a[i].x-a[i-1].x>1)
{
a[m].x=a[i].x-1;
a[m++].id=0; //ID置为0和原区间区别
}
}
sort(a,a+m,cmp);
int t=1,x=a[0].x; //t为区间重新编号
for(i=0;i<m;i++)
{
if(x!=a[i].x)
{
t++;
x=a[i].x;
}
if(a[i].id<0)
pos[-a[i].id-1][0]=t;
else if(a[i].id>0)
pos[a[i].id-1][1]=t;
}
memset(mark,0,sizeof(mark));
creat(1,1,t);
for(i=0;i<n;i++)
{
int l=pos[i][0];
int r=pos[i][1];
update(1,l,r,i);
}
ans=0;
query(1,1,t);
printf("%d\n",ans);
}
return 0;
}
poj 2528 Mayor's posters （线段树+区间离散）
原文：http://blog.csdn.net/u011721440/article/details/41774287