Mayor's posters

Mayor's posters"/>

Mayor's posters

题述《 .php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1528 》

#include<stdio.h>
#include<algorithm>
using namespace std;
struct post
{int l,r;
};
struct node
{int l,r;int iscovered;
};
node itree[160057];
int hashme[10000057];
void ibuild(int id,int l,int r)
{itree[id].l=l;itree[id].r=r;itree[id].iscovered=0;if(l==r) return ;ibuild(id*2+1,l,(l+r)/2);ibuild(id*2+2,(l+r)/2+1,r);
}
int iquery(int id,int l,int r)
{int res;int lres,rres;int i,j,k;if(itree[id].iscovered==1) return 0;if(itree[id].l==l&&itree[id].r==r)return itree[id].iscovered=1;if(r<(itree[id].l+itree[id].r)/2+1)res=iquery(id*2+1,l,r);else if(l>(itree[id].l+itree[id].r)/2)res=iquery(id*2+2,l,r);else{lres=iquery(id*2+1,l,(itree[id].l+itree[id].r)/2);rres=iquery(id*2+2,(itree[id].l+itree[id].r)/2+1,r);res=lres||rres;}if(itree[id*2+1].iscovered&&itree[id*2+2].iscovered)itree[id].iscovered=1;return res;
}
int main()
{int c,n;post p[10057];int pp[20057];int leafn;int res;int i,j,k;scanf("%d",&c);do{scanf("%d",&n);j=-1;for(i=0;i<n;++i){scanf("%d %d",&p[i].l,&p[i].r);pp[++j]=p[i].l;pp[++j]=p[i].r;}sort(pp,pp+j+1);j=unique(pp,pp+j+1)-pp;leafn=0;hashme[pp[0]]=leafn;for(i=1;i<j;++i){if(pp[i]-pp[i-1]==1) leafn+=1;else leafn+=2;hashme[pp[i]]=leafn;}ibuild(0,0,leafn);res=0;for(i=n-1;i>-1;--i)if(iquery(0,hashme[p[i].l],hashme[p[i].r])) ++res;printf("%d\n",res);}while(--c);return 0;
}

有序叠加范围集合，要求给出最终没有完全被覆盖的范围数量（依次叠加范围 (1,7) 、 (1,3) 和 (5,7) ，最终返回数量 3 ）。

范围着色（线段树）。至多 10000 张海报，至多 10000 个范围，至多 20000 个端点，墙至多被分成 19999 个部分（海报互不重叠，并且相邻海报至少相隔 1 个单位）。 19999 作为离散化的空间上限远小于 10000000 。（这里因为用海报端点瓷砖判定相隔关系，所以为了避免长度大于 2 的海报和相邻海报相隔大于 1 的空余部分的区分^（一），小改离散化如 71: else leafn+=2; 使通用。离散化的空间略涨成上限 39999 ^（二）。）为了方便（着完色即得出结果）从后向前着色。

（一）长度大于 2 的海报两端点之差大于 1 ，如果存在相邻海报之间有空余未被任何海报覆盖，因为通过海报端点判断的相隔关系，所以空余部分的右边海报左端点和左海报右端点之差也大于 1 。
（二）在^（一）的情况下，长度大于 2 的海报互不重叠并且相邻海报至少相隔 1 个单位离散化后都变成了长 3 的海报和长 1 的海报相隔空余部分， 3*10000+1*9999 。

算法《 / 》