牛客练习赛87 - B(写给自己)

B 题目: 给定一个permutation，求有多少个区间满足区间长度>=k,且第k小的数是x. 比赛的时候没有用心去观察，只是注意到和每两个比x小的数的位置有关系，想到差分，但是没写出来。赛后又观摩了带lao的思路。 思路1:观察到和区间端点所在位置有多少个数小于x有关，利用前缀和的思想。s[i]表示从1-i中有t个数小于x,如果一个区间有k-1个数比x小，那么x就是第k小。因此满足s[r] - s[l-1] = k-1的区间第k小的数是x，前提的包含x。接下来我们可以把=x的变成0。用前缀和加起来，即可得到s[i]。 如何保证区间包含x呢?区间右端点从x所在位置idx开始枚举，一直到n。左端点只记录x左侧的位置，这样区间的左端点在x左侧，右端点在x右侧，就可以满足包含x了。 如何统计满足的区间左端点的个数呢?用map预处理一下。比如我一个 1 4 5 3 2,x = 3。1、4、5位置小于x的数量是一样的。上述的s[r] - s[l-1] = k - 1,等价于s[l-1] = s[r] - k + 1。去map里查询满足这个等式关系的数就好了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i