AtCoderGC038BSortingaSegment的解题报告，能否详细解释长尾排序段落的算法原理？

本文共计1515个文字，预计阅读时间需要7分钟。

题目：给定一个长度为N的排列，只能对其长度为K的连续子序列进行一次从小到大的排序，问：排序之后能形成多少不同的排列？数据范围：1≤N≤1000，1≤K≤N

题意：给定一个长度为N的排列，你只能对其中长度为K的连续子序列进行一次从小到大的排序，问：排序之后能形成多少不同的排列？数据范围：1

题意：给定一个长度为N的排列，你只能对其中长度为K的连续子序列进行一次从小到大的排序，问：排序之后能形成多少不同的排列？

数据范围： 1 <= n, k <= 200,000， k <= n.

-----------------------------------分割线--------------------------------

分析此题，我们发现，长度为K的连续子序列在原排列中只有 N-K+1个，也就是说只会有N-K+1个排序情况，得出答案的上界N-K+1.

考虑上界中有多少连续子序列重复计数M，减去M即为答案。

那么剩下的问题就是统计每一个排序之后的连续子序列相同的个数M了。

朴素做法：枚举每一个长度为K的区间，从大到小排一下序，得出原排列，与其他排列进行比较，统计相同排列的个数cnt，累加每个cnt-1即可。

时间复杂度  O（N^2*Klog(K)）.

思考一下优化方法。

设原排列为A1，A2，A3，........，An。

假设一个区间[l，r]排序之后为原排列为P（l，r）.

那么如果P（l1，r1） = P（l2，r2）且 r1 - l1 +1 = r2 - l2 + 1 = K。