NBU 2475 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<<1 # define rson m+1,r,rt<<1|1 # define N 100005 int Max[N<<2],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<<1],Max[rt<<1|1]); } void Update(int pos,int x,int l,int r,int rt) { int m; if(l==r) { Max[rt]=x; return; } m=(l+r)>>1; 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=0; if(L<=l&&R>=r) return Max[rt]; m=(l+r)>>1; 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=0; for(i=1;i<=n;i++) { scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c); maxB=max(maxB,e[i].b); } sort(e+1,e+n+1); memset(Max,0,sizeof(Max)); memset(val,0,sizeof(val)); for(i=1;i<=n;i++) { L=e[i].b; R=e[i].c; if(Query(L,maxB,1,maxB,1)<R) { ans++; if(R>val[L]) //非常重要,只有比该点大的数才更新!不然会超时 { val[L]=R; Update(L,R,1,maxB,1); } } } printf("%d\n",ans); } return 0; }