【BZOJ 4282】慎二的随机数列

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4282
神犇题解：http://blog.csdn.net/PoPoQQQ/article/details/48998981

解题报告

首先我们需要得到一个结论：一定存在一组最优解，使得所有的模糊的位置均在LIS中
现在我们来证明一下这个结论：

考虑如果有一组最优解中存在一个模糊的位置不在最优解中
那么讲这个模糊的位置换成后面的第一个确定位置的数即可，这样不会使答案变劣

于是我们就假设一个确定的位置的前缀中有a个不确定位置
那么我们把该确定位置的值减去a（相当于把那a个不确定位置在值域上留出位置）
然后对确定的串做一次LIS，然后加上不确定位置的个数即可

Code

我写LIS一直用的BIT，但PoPoQQQ大爷的LIS似乎更加优雅
他是直接维护一个最优的LIS，然后每一次lower_bound就可以了！

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,tot,vout,_hash[N],f[N],arr[N];
char pat[10];

class Fenwick_Tree{
	int mx[N];
	public:
		inline void modify(int p, int v) {
			for (int i=p;i<=tot;i+=lowbit(i))
				mx[i] = max(mx[i], v);
		}
		inline int query(int p) {
			int ret = 0; 
			for (int i=p-1;i;i-=lowbit(i))
				ret = max(ret, mx[i]);
			return ret;
		}
	private:
		inline int lowbit(int x) {
			return x & (-x);
		}
}BIT;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read();
	for (int i=1;i<=n;++i) {
		scanf("%s",pat+1);
		if (pat[1] == 'K') {
			arr[++tot] = read() - m;
			_hash[tot] = arr[tot];		
		} else ++m;
	}
	n = tot; sort(_hash+1, _hash+1+tot);
	tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
	for (int i=1;i<=n;i++) {
		arr[i] = lower_bound(_hash+1, _hash+1+tot, arr[i]) - _hash;
		f[i] = BIT.query(arr[i]) + 1;
		vout = max(f[i], vout);
		BIT.modify(arr[i], f[i]);
	} 
	printf("%d\n",vout + m);
	return 0;
}