【BZOJ4282】慎二的随机数列

Description

间桐慎二是间桐家著名的废柴，有一天，他在学校随机了一组随机数列，准备使用他那强大的人工智能求出其最长上升子序列，但是天有不测风云，人有旦夕祸福，柳洞一成路过时把间桐慎二的水杯打翻了……

现在给你一个长度为 n 的整数序列，其中有一些数已经模糊不清了，现在请你任意确定这些整数的值，使得最长上升子序列最长（为何最长呢？因为间桐慎二向来对自己的人品很有信心）。

Input

第一行一个正整数 n。

接下来 n 行，第 i 行若为“K x” ，则表示第 i 个数可以辨认且这个数为 x；

若为“N” ，则表示第i 个数已经辨认不清了。

Output

第一行一个整数，表示最长的最长上升子序列长度。

Sample Input

4
K 1
N
K 2
K 3

Sample Output

HINT

对于100%的数据，n ≤ 100000，|x| ≤ 10^9

题解：一开始想得极其复杂，看了Claris的题解后也觉得极不可做，然而直到看到了这个做法：

先统计有多少个N，然后将N去掉，然后对于每个k，我们令它的值-=它前面N的个数，最后跑最长上升子序列即可。

不要问我为什么是正确的。。。如果两个K之间N的个数比这两个数的差要多，那么为什么不直接将这个K扔掉呢。。。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn=100010;

int n,m,sum;

int s[maxn];

char str[5];

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')	f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+(gc^'0'),gc=getchar();

	return ret*f;

}

int main()

{

	n=rd();

	int i,v,l,r,mid;

	for(i=1;i<=n;i++)

	{

		scanf("%s",str);

		if(str[0]=='K')

		{

			v=rd()-sum;

			l=1,r=m+1;

			while(l<r)

			{

				mid=(l+r)>>1;

				if(s[mid]<v)	l=mid+1;

				else	r=mid;

			}

			if(l>m)	m++;

			s[l]=v;

		}

		else	sum++;

	}

	printf("%d",m+sum);

	return 0;

}

慎二

【BZOJ4282】慎二的随机数列 乱搞