ZOJ1989 POJ1634 Who's the Boss

暴力を振るってもいいですが、少なくとも数百msはかかります.
ここでは神の哨兵を設置し、反復検索を使用しました.
まず給料順に並べ替えます.そしてxに対して、xの前の人のx-1の身長がxより低くなければ、x-1はxの上司(boss[x]=x-1)である.そうでなければ、x-1の上司boss[x-1]がxの上司かどうかをテストし、神の哨兵(神の哨兵はすべての人の上司に違いない)まで反復します.

/*******************************************************************************
 # Author : Neo Fung
 # Email : [email protected]
 # Last modified: 2012-06-11 21:30
 # Filename: ZOJ1989 POJ1634 Who's the Boss.cpp
 # Description : 
 ******************************************************************************/
#ifdef _MSC_VER
// #define DEBUG
#define _CRT_SECURE_NO_DEPRECATE
#endif

#include <fstream>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <limits.h>
#include <algorithm>
#include <math.h>
#include <numeric>
#include <functional>
#include <ctype.h>
using namespace std;

const int kMAX=30010;
const double kEPS=10E-6;

struct NODE
{
	int id,salary,height;
	bool operator<(const NODE &t) const
	{
		return salary>t.salary;
	}
}nodes[kMAX];

int map[1000000],subordinates[kMAX],boss[kMAX];

int inline FindBoss(const int &y,const int &x)
{
	if(!x)
		return 0;
	if(nodes[y].height>=nodes[x].height)	//  y x 
		return y;
	else return FindBoss(boss[y],x);		//  y x 
}

int main(void)
{
#ifdef DEBUG  
	freopen("../stdin.txt","r",stdin);
	freopen("../stdout.txt","w",stdout); 
#endif  

	int n,m,ncase=1,tmp;
	scanf("%d",&ncase);
	nodes[0].id=0;
	nodes[0].salary=nodes[0].height=(1<<30);	//  

	while(ncase--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)
			scanf("%d%d%d",&nodes[i].id,&nodes[i].salary,&nodes[i].height);
		sort(nodes+1,nodes+1+n);
		for(int i=0;i<=n;++i)
			map[nodes[i].id]=i;

		memset(subordinates,0,sizeof(subordinates));
		boss[0]=0;
		for(int i=1;i<=n;++i)
			boss[i]=FindBoss(i-1,i);
		for(int i=n;i>=1;--i)
			subordinates[boss[i]]+=(1+subordinates[i]);

		while(m--)
		{
			scanf("%d",&tmp);
			int x=nodes[boss[map[tmp]]].id;
			printf("%d %d
",x,subordinates[map[tmp]]);
		}
	}

	return 0;
}