题意:有一块足够长的墙了给竞选人贴海报,后贴的可能会把衣面贴的给覆盖掉,问最有多少不同的海报是能看到的。
思路:线段树,因为坐标范围太大,无法表示,得离散化。
1.如何离散化。个人觉得 离散化是件危险的事,因为每次都会漏掉特殊情况,如此题
若样列为
1 6
1 2
5 6
用unique离散后就得如下对应关系
1 1 2 5 6 6
0 1 2 3
如此求得的答案是能看见2块poster 因为它略去了中间的【3 4】段。但poj没有这样的测试数据,所以依然能过
如此求得的答案是能看见2块poster 因为它略去了中间的【3 4】段。但poj没有这样的测试数据,所以依然能过
所以离散化一定要特别特别注意区间被忽略的情况!!!!!。我用的方法是浪费一倍的空间,增加比它大一的点
如上例 pos 数组里将变以
pos : 1 1 2 2 2 3 5 6 6 6 7 7
这样原来漏掉的区点就由2这个点代替。
2.如何解些题。若按照它给的poster的顺序从前往后贴,你会发现无从下手,但是逆来,先贴后面的,贴它前一poster的时候,只要判断它的区间是否已被覆盖,覆盖了就不能再贴(因为是先把后来的poster给贴了)。
//1944K 47MS #include <stdio.h> #include <string.h> #include <algorithm> #define L(u) (u<<1) #define R(u) (u<<1|1) const int M = 10005; using namespace std; struct Node { int l,r; int cover; }node[M<<4]; struct Seg { int x,y; }seg[M]; int pos[M<<2]; void Build (int u,int left,int right) { node[u].l = left,node[u].r = right; node[u].cover = 0; if (node[u].l == node[u].r) return ; int mid = (node[u].l + node[u].r)>>1; Build (L(u),left,mid); Build (R(u),mid+1,right); } void Pushup(int u) //如果叶子都被覆盖了,则父结点的cover = 1 { if (node[L(u)].cover & node[R(u)].cover) node[u].cover = 1; } bool Query(int u,int left,int right) { if (node[u].cover) return false; if (pos[node[u].l] == left&&pos[node[u].r] == right)//离散化后的映射关系 { node[u].cover = 1; return true; } int mid = (node[u].l + node[u].r)>>1; bool flag; if (right <= pos[mid]) flag = Query(L(u),left,right); else if (left >= pos[mid+1]) flag = Query(R(u),left,right); else flag = Query(L(u),left,pos[mid])|Query(R(u),pos[mid+1],right); Pushup(u); return flag; } int main () { #ifdef LOCAL freopen("in.txt","r",stdin); #endif int i,T,n,x,y,m; scanf ("%d",&T); while (T --) { scanf ("%d",&n); int k = 0; for (i = 0;i < n;i ++) { scanf ("%d%d",&seg[i].x,&seg[i].y); //点增加1,避免离散化后,区间为遗漏 pos[k++] = seg[i].x,pos[k++] = seg[i].y; pos[k++] = seg[i].x+1,pos[k++] = seg[i].y+1; } sort (pos,pos + k); m = (unique(pos,pos+k) - pos - 1); Build (1,0,m); int ans = 0; for (i = n-1;i >= 0;i --) { if (Query(1,seg[i].x,seg[i].y)) ans ++; } printf ("%d\n",ans); } return 0; }