$O(nlogn)$求LIS&LCS长度

你怎么连这个都不会qwq

1.二分查找

在dp过程中维护单调栈d。

其中d[i]表示长度为i的LIS的最优结尾元素。

处理a[i]时，若它比结尾小，可以直接接上结尾元素a[len]。

若大于结尾，则需在结尾之前插入。

考虑维护的d具有单调性，采用二分。

严格上升（下降）中，使用upper_bound。

二分出第一个大于a[i]的数a[pos]。

需要替换它。

正确性证明：

因为二分出的pos为第一个比a[i]大的位置。

所以a[pos]>a[i]，可以发现，用a[i]替换a[pos]不会改变单调性。

因为pos+1就比a[i]小了。

并且a[i]显然作为lis的结尾要比a[pos]优。

len=1;
for(int i=2;i<=n;i++)
	if(d[len]>=a[i])d[++len]=a[i];
	else {
		int pos=upper_bound(d+1,d+1+len,a[i])-d;
		d[pos]=a[i];
	}

2.树状数组

过程中维护前缀最大值就好了。