首页 > 代码库 > 12D-三维线段树

12D-三维线段树

给你N个女人的B,I,r,女人之间如果Bi<Bj&&Ii<Ij&&Ri<Rj,那么i女人就会去自杀!问总共有多少个女人自杀

 

#include<cstdio>#include<map>#include<cstring>#include<algorithm>using namespace std;const int maxn = 500010;const int inf = 1<<30;struct node{    int b,i,l;    bool operator<(const node &x) const    {        if(b==x.b)        {            if(i==x.i)            {                return l < x.l;            }            return i > x.i;        }        return b < x.b;    }}ji[maxn];int main(){    int n;    map<int,int> mp;    map<int,int>::iterator it;    scanf("%d",&n);    for(int i=1;i<=n;i++)        scanf("%d",&ji[i].b);    for(int i=1;i<=n;i++)        scanf("%d",&ji[i].i);    for(int i=1;i<=n;i++)        scanf("%d",&ji[i].l);    sort(ji+1,ji+n+1);    mp[inf] = -inf;    mp[-inf] = inf;    int res = 0;    for(int i=n;i>=1;i--)    {        it = mp.upper_bound(ji[i].i);        if(ji[i].l<it->second)            res++;        else if(mp[ji[i].i]<ji[i].l)        {            mp[ji[i].i] = ji[i].l;            for(it = --mp.lower_bound(ji[i].i);it->second<=ji[i].l;)                mp.erase(it--);        }    }    printf("%d\n",res);}

 

12D-三维线段树