Lucky

codeforces1768D_timidcatt的博客-CSDN博客

思路一个置换环内产生的逆序对最少为n-1例如在n4时2,3,4,1构成的置换环。

首先如果数组中有大于k的数答案肯定是0所以在k小于等于0时有答案的充要条件也就是存在a[i]k。

然后因为数组中有负数而要想和k肯定要选正数那么我们选择的正数之间肯定还会夹杂负数为了尽量产生少的影响所以要保持p[i]i因为递增数组的逆序对数量为0每交换一对相邻数都会使逆序对数量改变1那么就会产生如2,5,6,3,4,1这样的置换环排列置换环部分也就是2,5,6,1这部分产生的贡献就是环的大小-1,中间的3,4分别会与环最右边的数和左边环中第一个数产生一个逆序对所以中间不在环中的每一个数贡献都是2所以对于一个满足要求的区间它的答案即为区间长度-环的大小*2环的大小-1区间长度*2-换的大小

然后我们找这样的区间可以贪心一下我们从上面的式子可以看出要想答案最小就要找一个最短的区间并且使里面的环的大小最大。

要找一个最短的区间显然需要区间端点都是正数可以用尺取的方式找到这样的一个区间要是区间里的环最大区间里的大于等于0的数肯定都选负数就要用一个大根堆存起来在找到合法区间后尽可能加上大的负数这样就能使得答案最小

//#include__msvc_all_public_headers.hpp

#includebits/stdc.h

{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int

t;t

a[j];cnt;//记录环的大小}else{out.push(a[j]);//记录区间内的负数}if

(sum