n個女性中,如果有一個女性的三維比這個女性的三維都大,這個女性就要自殺。問要自殺多少個。
思路分析:
先按照第一維排序。
然後離散化第二維,用第二維的下標建樹,樹上的值是第三維,更新的時候取最大值。
注意是按照第一維度從大到小進入線段樹。
而且還要嚴格遞增。
所以處理第一維度比較大小的時候要分開處理,要把相同的先判斷,再更新入樹。
那麼如何判斷這個女性是否自殺。
首先,你知道第一維度是從大到小的,所以先進樹了的節點的第一維度一定更大。
再次,我們考慮第二維度,我們去樹上第二維度下標大的節點區去尋找第三維度。
如果有一個比這個的第三維度大,那麼就滿足。
#include#include #include #include #define lson num<<1,s,mid #define rson num<<1|1,mid+1,e #define maxn 500005 using namespace std; struct node { int a,b,c; bool operator < (const node &cmp)const { if(a!=cmp.a)return a >1; build(lson);build(rson); } void update(int num,int s,int e,int pos,int val) { if(s==e) { res[num]=max(res[num],val); return; } int mid=(s+e)>>1; if(pos<=mid)update(lson,pos,val); else update(rson,pos,val); pushup(num); } int query(int num,int s,int e,int l,int r) { if(l<=s && r>=e)return res[num]; int mid=(s+e)>>1; if(r<=mid)return query(lson,l,r); else if(l>mid)return query(rson,l,r); else return max(query(lson,l,mid),query(rson,mid+1,r)); } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&wm[i].a); for(int i=1;i<=n;i++) { scanf("%d",&wm[i].b); x[i]=wm[i].b; } for(int i=1;i<=n;i++) scanf("%d",&wm[i].c); sort(wm+1,wm+1+n); sort(x+1,x+1+n); int m=unique(x+1,x+1+n)-x; m--; int last=wm[n].a; int r=n; int l=n; int ans=0; wm[0].a=0x3f3f3f3f; for(int i=n;i>=1;) { while(wm[l].a==last) { l--; } int c=r; while(c>l) { int pos=lower_bound(x+1,x+m+1,wm[c].b)-x; if(pos+1<=m && query(1,1,m,pos+1,m)>wm[c].c)ans++; c--; } c=r; while(c>l) { int pos=lower_bound(x+1,x+m+1,wm[c].b)-x; update(1,1,m,pos,wm[c].c); c--; } i=l;r=l;last=wm[i].a; } printf("%d\n",ans); return 0; }