冷知识，这题和 KMP 算法有 000 个关系。
注意到 M 只有一个，而一个 KMP 的子序列必须需要一个 M 前面的 K，M，M 之后的 P，所以我们不妨编个样例：
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPKKRMWYSWDPPHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
能够组成的 KMP 子序列有：
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{green}K\color{black}APTAPPKKR\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}PKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPP\color{green}K\color{black}KR\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}PKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWD\color{blue}P\color{black}PHIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWDP\color{blue}P\color{black}HIGROSQIDONGPKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
KAPTAPPKKRMWYSWDPPHIGROSQIDONGP\tt \color{black}KAPTAPPK\color{green}K\color{black}R\color{red}M\color{black}WYSWDPPHIGROSQIDONG\color{blue}PKAPTAPPKKRMWYSWDPPHIGROSQIDONGP
可以发现总共子序列数量就是 M 之前的 K 的数量和 M 之后 P 的数量之积。
时间复杂度 O(∣s∣)O(|s|)O(∣s∣)。
好了，你已经学会这一题了，现在来完成这一题吧：三元上升子序列_信奥算法普及+/提高-ACGO题库
hints：树状数组可以当做集合使用，可以以 O(logV)O(\log V)O(logV) 的时间复杂度快速往集合内加入、删除一个不超过 VVV 的元素，查询集合内小于等于某个元素的数量。
