题目地址
要用到离散化
一直Runtime Error 发现原因是数组开在main() 函数里 应该是开不下导致的
还有个问题：
bool b1=post(root->pLeft,s,mid);
bool b2=post(root->pRight,mid+1,e);
covered=b1||b2;
竟然与
covered=post(root->pLeft,s,mid)||post(root->pRight,mid+1,e);
结果不一样.....
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct CPoster{int L,R;
}pos[10100];
struct CNode{int L,R;bool Covered; //true 表示完全被覆盖 int Mid(){return (L+R)/2;}CNode *pLeft,*pRight;
}tree[1000000];
int point[20200],hash[10000010];
int nNode=0;
void BuildTree(CNode *root,int s,int e)
{root->L=s;root->R=e;root->Covered=false;if(s==e) return;int mid=root->Mid();root->pLeft=++nNode+tree;root->pRight=++nNode+tree;BuildTree(root->pLeft,s,mid);BuildTree(root->pRight,mid+1,e);
}
bool post(CNode *root,int s,int e)
{ //true=部分或全部可见 if(root->Covered) return false; if(root->L==s&&root->R==e){root->Covered=true; //标记为覆盖 return true;}int mid=root->Mid();bool covered;if(e<=mid) covered=post(root->pLeft,s,e);else if(s>mid) covered=post(root->pRight,s,e);else {bool b1=post(root->pLeft,s,mid);bool b2=post(root->pRight,mid+1,e);covered=b1||b2;}if(root->pLeft->Covered&&root->pRight->Covered)root->Covered=true;return covered;
}
int main()
{int T;scanf("%d",&T);while(T--){int n;int cnt=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&pos[i].L,&pos[i].R);point[cnt++]=pos[i].L;point[cnt++]=pos[i].R;}sort(point,point+cnt);cnt=unique(point,point+cnt)-point;int nInterval=0;for(int i=0;i<cnt;i++)hash[point[i]]=nInterval++;nNode=0;BuildTree(tree,0,nInterval);int ans=0;for(int i=n-1;i>=0;i--)if(post(tree,hash[pos[i].L],hash[pos[i].R])) ans++;printf("%d\n",ans);}return 0;
}