传送门：POJ2528 Mayor's posters
有时，区间的端点不是整数，或者区间过大而导致建树内存开销过大。这时，我们需要离散化后建树。
以下,直接先附上郭炜老师的代码：
#include <iostream>
#include <algorithm>
#include<cstdio>
#include <math.h>
using namespace std;int n;
struct CPost{int L,R;
};CPost posters[10100];
int x[20200]; //存放所有海报的端点瓷砖编号
int hash[10000010]; //hash[i]表示瓷砖i所处的离散化后的区间编号
struct CNode{int L,R;bool bCovered; //区间[L,R]是否已经被完全覆盖CNode * pLeft, * pRight;
};CNode Tree[1000000];
int nNodeCount = 0;int Mid( CNode * pRoot){return (pRoot->L + pRoot->R)/2;
}void BuildTree( CNode * pRoot, int L, int R){pRoot->L = L;pRoot->R = R;pRoot->bCovered = false;if( L == R )return;nNodeCount ++;pRoot->pLeft = Tree + nNodeCount;nNodeCount ++;pRoot->pRight = Tree + nNodeCount;BuildTree( pRoot->pLeft,L,(L+R)/2);BuildTree( pRoot->pRight,(L+R)/2 + 1,R);
}bool Post( CNode *pRoot, int L, int R) {//插入一张正好覆盖区间[L,R]的海报,返回true则说明区间[L,R]是部分或全部可见的if( pRoot->bCovered ) return false;if( pRoot->L == L && pRoot->R == R) {pRoot->bCovered = true; return true;}bool bResult ;if( R <= Mid(pRoot) )bResult = Post( pRoot->pLeft,L,R);else if( L >= Mid(pRoot) + 1) bResult = Post( pRoot->pRight,L,R);else {bool b1 = Post(pRoot->pLeft ,L,Mid(pRoot));bool b2 = Post( pRoot->pRight,Mid(pRoot) + 1,R);bResult = b1 || b2;}//要更新根节点的覆盖情况if( pRoot->pLeft->bCovered && pRoot->pRight->bCovered )pRoot->bCovered = true;return bResult;
}int main()
{int t;int i,j,k;scanf("%d",&t);int nCaseNo = 0;while(t--) {nCaseNo ++;scanf("%d",&n);int nCount = 0;for( i = 0;i < n;i ++ ) {scanf("%d%d", & posters[i].L,& posters[i].R );x[nCount++] = posters[i].L;x[nCount++] = posters[i].R;}sort(x,x+nCount);nCount = unique(x,x+nCount) - x; //去掉重复元素//下面离散化int nIntervalNo = 0;for( i = 0;i < nCount;i ++ ) {hash[x[i]] = nIntervalNo;if( i < nCount - 1) {if( x[i+1] - x[i] == 1)nIntervalNo ++;elsenIntervalNo += 2;}}BuildTree( Tree,0,nIntervalNo );int nSum = 0;for( i = n - 1;i >= 0;i -- ) { // 从后往前看每个海报是否可见if( Post(Tree,hash[posters[i].L],hash[posters[i].R]))nSum ++;}printf("%d\n",nSum);}return 0;
}
改过的
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e4+10;
const int maxl=1e7+10;
int n;
struct Post{int L,R;
}posters[maxn];int x[maxn*2]; //存放所有海报的端点的瓷砖编号
int Hash[maxl]; //Hash[i]表示瓷砖i所处的离散后的区间编号struct Node{int L,R;bool bCovered; //区间[L,R]是否已被完全覆盖Node *pLeft,*pRight;
}Tree[maxn*17]; //cnt最大2*maxn,nIntervalNo最大2*cnt=4*maxn,线段树最好开四倍16*maxn，有点小，开到17*maxnint nNodeCnt=0;int Mid(Node *pRoot){return (pRoot->L+pRoot->R)>>1;
}void BuildTree( Node * pRoot, int L, int R){pRoot->L = L;pRoot->R = R;pRoot->bCovered = false;if( L == R )return;nNodeCnt ++;pRoot->pLeft = Tree + nNodeCnt;nNodeCnt ++;pRoot->pRight = Tree + nNodeCnt;int mid=L+((R-L)>>1);BuildTree( pRoot->pLeft,L,mid);BuildTree( pRoot->pRight,mid+1,R); /*这里注意mid+1!=mid|1, 0|1=1,1|1=1,根据“或”运算的运算法则，当mid二进制最后一位是1时，再或1值不变。x<<1|1，对于这种x左移一位，最后一位肯定是0，再或1相当于加1*/
}bool Post( Node *pRoot, int L, int R) {//插入一张正好覆盖区间[L,R]的海报,返回true则说明区间[L,R]是部分或全部可见的if( pRoot->bCovered ) return false;if( pRoot->L == L && pRoot->R == R) {pRoot->bCovered = true; return true;}bool bResult ;if( R <= Mid(pRoot) )bResult = Post( pRoot->pLeft,L,R);else if( L >= Mid(pRoot) + 1) bResult = Post( pRoot->pRight,L,R);else {bool b1 = Post(pRoot->pLeft ,L,Mid(pRoot));bool b2 = Post( pRoot->pRight,Mid(pRoot) + 1,R);bResult = b1 || b2;}//要更新根节点的覆盖情况if( pRoot->pLeft->bCovered && pRoot->pRight->bCovered )pRoot->bCovered = true;return bResult;
}int main(){int t;scanf("%d",&t);while(t--){scanf("%d",&n);int cnt=0;for(int i=0;i<n;i++){scanf("%d%d",&posters[i].L,&posters[i].R);x[cnt++]=posters[i].L;x[cnt++]=posters[i].R;}sort(x,x+cnt);cnt=unique(x,x+cnt)-x; //去掉重复元素//下面离散化int nIntervalNo=0;for(int i=0;i<cnt;i++){Hash[x[i]]=nIntervalNo;if(i<cnt-1){if(x[i+1]-x[i]>1) nIntervalNo+=2;else nIntervalNo++;}}BuildTree(Tree,0,nIntervalNo);int nSum=0;for(int i=n-1;i>=0;i--){ // 从后往前看每个海报是否可见if( Post(Tree,Hash[posters[i].L],Hash[posters[i].R]))nSum ++;}printf("%d\n",nSum);}return 0;
}