JZOJ4214. SERN的野望

Description

Error! Human is dead. Mismatch.
SERN妄图研发出时间机器，然而现在却只有一堆失败的实验品。
然而，SERN妄图通过这些失败的试验品研究出正确的道路，而这首先就需要将这些失败的实验品归类。
每一个实验品有一个转移强度D和转移距离R。由于SERN血腥残忍、不择手段，所以所有实验品的转移强度均不相同，转移距离也均不相同。
SERN惊讶的发现，一个时间机器的性能极大地取决于它在高斯平面上的投影。
定义一个时间机器α在高斯平面上的投影λ(α)“傅里叶包含”【“傅里叶包含"记作”)("】另一个时间机器β在高斯平面上的投影λ(β)【此关系记作"α)(β"】，当且仅当α的转移强度大于β的转移强度且α的转移距离大于β的转移距离。
定义黎曼-洛伦兹函数ζ(A,S)为真当且仅当在实验品集合S中的任何实验品在高斯平面上的投影都不傅里叶包含实验品A在高斯平面上的投影，亦即对于任意B∈S，"B)(A"不成立。
而对实验品的归类方式可以分为以下几个步骤：
S1：令i=0
S2：令i=i+1 令S=还没被分组的实验品集合
S3：对于每一件S中的武器A，如果黎曼-洛伦兹函数ζ(A,S)为真，则将武器A标记为第i组
【注意S在这个过程中始终保持不变，这称为分组的牛顿-科特斯一致性】
S4：如果所有实验品均被分组则结束，否则转S2

给定N个实验品的D和R，你的任务是将其分组。

Input

输入文件的第一行包含一个正整数N，表示实验品的个数。
接下来N行，每行两个正整数D,R，描述一个实验品的D和R.

Output

输出文件包含N行，每行一个正整数，第i行的数表示第i个实验品被分在了哪一组。

Sample Input

5
1 4
2 2
3 3
4 1
5 5

Sample Output

2
3
2
2
1

Data Constraint

对于20%的数据，N<=100
对于40%的数据，N<=3000
对于100%的数据，N<=100000，1<=R,D<=10^9

Solution

题目描述非常扯淡。。。
其实就是一组组选出满足D_p>D_a且R_p>R_a的实验品p（a，p都是剩余实验品）
画成图较好理解
一张丑陋的图

这图花了我整整1分钟呢
可以发现，只要某个点的右上方没有点，就可以选
那么容易发现，只要以D为第一关键字，R为第二关键字从大到小排序
然后记录每一组的最右边的点的坐标cur[i]
每次加一个点时二分找到第一个能放进去的组（即当前的R>cur[mid]）
记录ans即可

Code

#include<bits/stdc++.h>
#define open_in(x) freopen(""#x".in","r",stdin);
#define open_out(x) freopen(""#x".out","w",stdout);
#define open_(x) freopen(""#x".in","w",stdout);
#define open(x) open_in(x);open_out(x);
#define mes(x,y) memset(x,y,sizeof(x));
#define mec(x,y) memcpy(x,y,sizeof(x));
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int X=100010;
const int M=1e9+7;

template<class T>
inline void read(T &x)
{
	int f=1;char ch=getchar();x=0;
	while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}

struct Point
{
	int x,y,ID;
}p[X];
bool cmp(Point a,Point b){return (a.x>b.x)||(a.x==b.x && a.y>b.y);}

int cur[X],len=0,ans[X];

int binary(int x)
{
	int l=1,r=len,mid,ls=len+1;
	while (l<=r)
	{
		mid=(l+r)/2;
		if (cur[mid]<x)
			r=(ls=mid)-1;
		else
			l=mid+1;
	}
	return ls;
}

int n;
int main()
{
	open(SERN);
	read(n);
	register int i;
	for (i=1;i<=n;i++)
		read(p[i].x),read(p[i].y),p[i].ID=i;

	sort(p+1,p+n+1,cmp);

	for (i=1;i<=n;i++)
	{
		int q=binary(p[i].y);
		if (q>len)
			cur[++len]=p[i].y,ans[p[i].ID]=len;
		else
			cur[q]=p[i].y,ans[p[i].ID]=q;
	}

	for (i=1;i<=n;i++)
		printf("%d\n",ans[i]);
	return 0;
}