题意：
有N (1 ≤ N ≤ 500000)个女士去参加舞会。每个女士有三个值ai,bi,ci。如果女士i发现有其它女士的这三个值都比自己高的话就会去跳楼--||.现在问你最后会有多少跳楼的女士。
思路：
以前没做过这样的线段树。其实还是蛮有意思的。先按a大的在前面排序如果这样我们就可以保证。只有排在前面的女士才可能逼死排在后面的女士。现在要解决的就是怎么判断一个女士会不会自杀了。我们可以将b离散化。用一颗线段树维护在b值为b时c的最大值。我们就可以查询b值大于b时c值的最大值。然后我们按排序的顺序将每个女士加进线段树。要注意的是a值相同的必须先计算完在加进线段树。以为必须保证线段树里的女士的a值都比现在大。这样就可以判断了。
详细见代码：
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=500100;
typedef long long ll;
#define lson L,mid,ls
#define rson mid+1,R,rs
int mav[maxn<<2],H[maxn],m,n;
struct node
{
int x,y,z;
} wo[maxn];
bool cmp(node a,node b)
{
return a.y>b.y;
}
void build(int L,int R,int rt)
{
mav[rt]=0;
if(L==R)
return ;
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
build(lson);
build(rson);
}
void update(int L,int R,int rt,int p,int v)
{
if(L==R)
{
mav[rt]=max(mav[rt],v);
return;
}
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1;
if(p<=mid)
update(lson,p,v);
else
update(rson,p,v);
mav[rt]=max(mav[ls],mav[rs]);
}
int qu(int L,int R,int rt,int l,int r)
{
if(l<=L&&R<=r)
return mav[rt];
int ls=rt<<1,rs=ls|1,mid=(L+R)>>1,val=0;
if(l<=mid)
val=max(val,qu(lson,l,r));
if(r>mid)
val=max(val,qu(rson,l,r));
return val;
}
void init()
{
sort(H,H+m);
m=unique(H,H+m)-H;
build(1,m,1);
for(int i=0;i<n;i++)
wo[i].x=lower_bound(H,H+m,wo[i].x)-H+1;
sort(wo,wo+n,cmp);
}
int main()
{
int i,j,k,ans;
while(~scanf("%d",&n))
{
for(i=0;i<n;i++)
{
scanf("%d",&wo[i].x);
H[i]=wo[i].x;
}
for(i=0;i<n;i++)
scanf("%d",&wo[i].y);
for(i=0;i<n;i++)
scanf("%d",&wo[i].z);
m=n,ans=0;
init();
for(i=0;i<n;i=j)//y从小到大保证线段树中的y都比当前y大。
{
j=i;
while(j<n&&wo[j].y==wo[i].y)
{
if(qu(1,m,1,wo[j].x+1,m)>wo[j].z)
ans++;
j++;
}
for(k=i;k<j;k++)
update(1,m,1,wo[k].x,wo[k].z);//线段树维护值为x范围[L,R]间z的最大值
}
printf("%d\n",ans);
}
return 0;
}