Survivors
题目链接:http://acm.nbu.edu.cn/v1.0/Problems/Problem.php?pid=2475
题意:给定n个人,每个人有strength,dexterity,intelligence3个属性! 如果在这n个人当中存在某个人3项属性都不比他小，这个人则淘汰！否则生存下来，求最后生存下来的人数!
思路:按3个属性优先从大到小排序!那么对于当前幸存者i,因为之前的[1,i-1]幸存者的strength都比他大,如果存在dexterity比他大的人当中intelligence也比他大，则这个人淘汰！我们只要求出在[1,i-1]个人当中比i的dexterity属性大的这些人当中的intelligence的最大值即可! 即求[dexterity,INF]区间内intelligence的最大值即可!
所以可以利用线段树动态维护dexterity区间最大值，转换成了RMQ线段树!
注意:在比当前值大时才更新最大值,不然会超时
# include<cstdio>
# include<cstring>
# include<algorithm>
using namespace std; # define lson l,m,rt<<
# define rson m+,r,rt<<|
# define N int Max[N<<],val[N]; struct node
{
int a,b,c; //strength dexterity intelligence
node(){};
node(int aa,int bb,int cc):a(aa),b(bb),c(cc){};
bool operator < (const node &B)const
{
if(a==B.a)
{
if(b==B.b)
return c>B.c;
return b>B.b;
}
return a>B.a;
}
}e[N]; void PushUp(int rt)
{
Max[rt]=max(Max[rt<<],Max[rt<<|]);
} void Update(int pos,int x,int l,int r,int rt)
{
int m;
if(l==r)
{
Max[rt]=x;
return;
}
m=(l+r)>>;
if(pos<=m) Update(pos,x,lson);
else Update(pos,x,rson);
PushUp(rt);
} //查询[L,R]内的最大值
int Query(int L,int R,int l,int r,int rt)
{
int m,ans=;
if(L<=l&&R>=r)
return Max[rt];
m=(l+r)>>;
if(L<=m) ans=max(ans,Query(L,R,lson));
if(R>m) ans=max(ans,Query(L,R,rson));
return ans;
} int main()
{
int T,i,n,ans,L,R,maxB;
while(scanf("%d",&n)!=EOF)
{
ans=maxB=;
for(i=;i<=n;i++)
{
scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
maxB=max(maxB,e[i].b);
}
sort(e+,e+n+);
memset(Max,,sizeof(Max));
memset(val,,sizeof(val));
for(i=;i<=n;i++)
{
L=e[i].b;
R=e[i].c;
if(Query(L,maxB,,maxB,)<R)
{
ans++;
if(R>val[L]) //非常重要,只有比该点大的数才更新!不然会超时
{
val[L]=R;
Update(L,R,,maxB,);
}
}
}
printf("%d\n",ans);
}
return ;
}
NBU 2475