求昨天 AGC C 题题解简单解释

倒也不需要把题解整个翻译一下 （我觉得也没人愿意这么干）

就是大概解释一下题解在说些啥，实在是没看懂他说的，谢谢各位神们qwq

Let’s now consider any consecutive segment of Ks (bounded by ends of the permutation or by K−1s). Let L be the element to the left end of this segment, or 0 if there isn’t any, and R be the element to the right of this segment, or N+1 if there isn’t any. Clearly, no element from this segment that doesn’t lie in [L+1,R−1] can ever be in any longest increasing subsequence of P, so let’s consider only elements from this range. Denote them Q_1,Q_2,\cdot\cdot\cdot,Q_M , and denote the length of the longest increasing subsequence of Q as K_1

It’s easy to see that K is equal to the number of i with A_i=K-1, plus the sum of K_1 over all these segments. Indeed, we have to take all i with A_i=K-1 to every LIS, and the maximum number of elements that we can fit “in between” two such adjacent K-1s (or ends) is precisely the corresponding K_1.

从这两段开始看不懂的qwq 尤其是那个 segment 不知道干啥的