【2021 Multi-University 4 G】Increasing Subsequence 题解

题目大意

  给定一个排列 $a_1,\cdots,a_n$，求极长上升子序列的数量。

  $n \le 10^5$

$$\\$$ $$\\$$ $$\\$$

题解

  设 $dp_i$ 表示以 $i$ 结尾的极长上升子序列数量，那么关键就是找到 $dp_i$ 能从哪些 $dp_j$ 转移过来，需要满足 $a_i>a_j$ 且 $j$ 到 $i$ 之间没有 $\in [a_j,a_i]$ 的数了。
  这种前面的数贡献到后面的数的模型，还要想到 cdq 这种！
  假设当前分治区间 $[l,r]$，中间是 $mid$。把 $a_l,\cdots,a_r$ 从小到大排序，然后左半边维护一个位置单调递减的栈，右半边维护一个位置单调递增的栈，大概长这样：

$$7\ 6\ 3\ 1\ |\ 2\ 4\ 5\ 8$$

  （中线代表 $mid$，两边分别是向左向右增长的栈，数字是 $a$ 值，保持了原序列的相对位置关系）
  左边的单调栈的含义是，如果有一个很大的数放在了很右的位置，显然它左边的小的数都不再能转移出去了；右边的单调栈的含义是，因为右边是代表询问的，因此如果有一个很大的数放在了很左的位置，那么它会对以后的询问构成更紧的限制，它右边的小的数就没用了。
  那么比如 $8$ 插入到右边的栈，它的栈里下一个元素是 $5$，意思就是左边 $5$ 及以下的数都不能转移到 $8$，因此能转移到 $8$ 的只有 $6,7$。那么这就是个在左边栈里二分的过程。
  复杂度 $O(n \log ^2 n)$

代码

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=1e5+5;
const LL mo=998244353;

int n,a[maxn];
bool canBeInit[maxn];

LL dp[maxn],Sl[maxn];
int b0,zl0,zl[maxn],zr0,zr[maxn];
pair<int,int> b[maxn];
int find(int x) {
	int l=1, r=zl0;
	while (l<=r) {
		int mid=(l+r)>>1;
		if (a[zl[mid]]<x) l=mid+1; else r=mid-1;
	}
	return l-1;
}
void cdq(int l,int r) {
	if (l==r) {
		(dp[l]+=canBeInit[l])%=mo;
		return;
	}
	int mid=(l+r)>>1;
	cdq(l,mid);
	
	b0=0;
	fo(i,l,r) b[++b0]=make_pair(a[i],i);
	sort(b+1,b+1+b0);
	zl0=zr0=0;
	fo(i,1,b0) if (b[i].second<=mid) {
		while (zl0 && zl[zl0]<b[i].second) zl0--;
		zl[++zl0]=b[i].second;
		Sl[zl0]=(Sl[zl0-1]+dp[b[i].second])%mo;
	} else {
		while (zr0 && zr[zr0]>b[i].second) zr0--;
		int t=find(a[zr[zr0]]);
		(dp[b[i].second]+=Sl[zl0]-Sl[t]+mo)%=mo;
		zr[++zr0]=b[i].second;
	}
	
	cdq(mid+1,r);
}

int main() {
	int T;
	scanf("%d",&T);
	while (T--) {
		scanf("%d",&n);
		fo(i,1,n) scanf("%d",&a[i]);
		
		int last=n+1;
		fo(i,1,n) if (a[i]<last) {
			canBeInit[i]=1;
			last=a[i];
		} else canBeInit[i]=0;
		
		memset(dp,0,sizeof(LL)*(n+2));
		cdq(1,n);
		
		last=0;
		LL ans=0;
		fd(i,n,1) if (a[i]>last) {
			last=a[i];
			(ans+=dp[i])%=mo;
		}
		
		printf("%lld\n",ans);
	}
}