【NOI2014模拟6.20】慎二的随机数列

本文主要是介绍【NOI2014模拟6.20】慎二的随机数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

Data Constraint

对于10%的数据，n ≤ 1000，不存在“N”。

对于30%的数据，“N”的个数≤ 20，0 ≤ x ≤ 100000。

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

Solution

乍一看就是最长上升子序列
但是N可以取任意数，而序列中又必须上升而不能有相等的，这就比较麻烦了
一种显然的想法是N就去比当前序列大1的数，但是N可以作为一个子序列的开头，可以取最小值
那么想一下当N取任意数时，只有选比目前在子序列的队列中（就是正常时用来二分的序列）大1，也就是比这个队列中的每个数大1时，才会有最优的贡献，也就是这个队列的每一项可以等于它的前一项+1。
这个就很显然了，可以用线段树，但是有更加好打的方法
把这个+1操作，可以转换为把原来的每一个数往后移一位，然后全部+1，再在队头加一个最小值就行了
答案就是这个队列的长度

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 201000
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int n,a[N],s[N],tot,ans,ls,to;
int find(int x)
{int l=to,r=tot;while(l+1<r){int m=(l+r)/2;if(s[m]+ls<x) l=m;else r=m;}if(s[r]+ls<x) l=r;return l;
}
int main()
{freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);scanf("%d\n",&n);fo(i,1,n){char y;scanf("%c",&y);if(y=='N') a[i]=-2000000000;else scanf("%d",&a[i]);scanf("\n");}tot=100010;to=tot;ls=0;s[tot]=-2000000000;fo(i,1,n){int x=a[i];if(x==-2000000000) {ls++,s[--to]=-2000000000-ls;}else{if(x>s[tot]+ls) s[++tot]=x-ls;else s[find(x)+1]=x-ls;}}printf("%d\n",tot-to);
}