[codeforces][ball][线段树]

原题链接：http://codeforces.com/contest/12/problem/D

给一系列三维点(x,y,z)。求出满足以下条件的点个数： 对点 (x1,y1,z1 ) ,  存在一个点 (x2,y2,z2)  使得 x2> x1, y2> y1, z2> z1。

先按 x 从大到小排序，再将 y 离散化。从前到向扫描，对于点(x,y,z), 在大于 y 的区间内找到最大的 z1，如果 z1> z, 则答案加 1.

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

int const N= 500100;
int tb[N<<2]= {0};
int n;

struct Node{
	int x, y, z;
};

bool operator<( Node a, Node b ){
	return a.x> b.x;
}

Node dat[N];
int num[N];

int query( int x, int y, int L, int R, int rt ){
	if( x== L && y== R ) return tb[rt];
	
	int mid= (L+ R)>>1;
	if( y<= mid ) return query( x, y, L, mid, rt<<1 );
	else if( x> mid ) return query( x, y, mid+ 1, R, rt<<1|1 );
	else{
		int a= query( x, mid, L, mid, rt<<1 );
		int b= query( mid+ 1, y, mid+ 1, R, rt<<1|1 );
		
		return max(a,b);
	}
}

void update( int x, int d, int L, int R, int rt ){
	if( L== R ){
		tb[rt]= max( tb[rt], d );
		return;
	}
	
	int mid= (L+ R)>>1;
	if( x<= mid ) update( x, d, L, mid, rt<<1 );
	else update( x, d, mid+ 1, R, rt<<1|1 );
	
	tb[rt]= max( tb[rt<<1], tb[rt<<1|1] );
}

int main(){
	scanf("%d", &n );
	for( int i= 1; i<= n; ++i ) scanf("%d", &dat[i].x );
	for( int i= 1; i<= n; ++i ){ scanf("%d", &dat[i].y ); num[i]= dat[i].y; }
	for( int i= 1; i<= n; ++i ) scanf("%d", &dat[i].z );

	sort( dat+ 1, dat+ 1+ n );
	sort( num+ 1, num+ 1+ n );
	
	int ans= 0, i, j, pre= 1;
	for( i= 1; i<= n; i= j ){
		for( j= i; j<= n && dat[j].x== dat[i].x; j++ ){
			int pos= lower_bound( num+ 1, num+ 1+ n, dat[j].y )- num;
			
			if( pos== n ) continue;
			
			int Max= query( pos+ 1, n, 1, n, 1 );
			if( Max> dat[j].z ) ans++;
		}
		
		for( j= i; j<= n && dat[j].x== dat[i].x; j++ ){
			int pos= lower_bound( num+ 1, num+ 1+ n, dat[j].y )- num;
			
			update( pos, dat[j].z, 1, n, 1 );
		}
	}
	
	printf("%d\n", ans );

	return 0;
}