ABC229G Longest Y 做题记录

给你一个字符串 SS,由 Y. 构成。

现在你可以最多进行 kk 次操作,每次可以交换两个相邻的字符。

请你求出最多 kk 次操作后,最长连续字符 Y 的长度。

  • 2S2×1052 \leq |S| \leq 2 \times 10^5
  • 0K10120 \leq K \leq 10^{12}

AASSY 的位置从小到大构成的序列,令 Bi=AiiB_i=A_i-i,那么问题就转化为:

每次操作可以选择一个 ii,让 BiBi+1B_i\to B_i+1 或者 BiBi1B_i\to B_i-1,最多进行 kk 次操作,求操作之后最长的 BiB_i 相同的连续段。

考虑尺取,假设当前区间为 [l,r][l,r],那么最少需要的操作次数显然就相当于这个函数的最小值:

f(x)=i=lrBixf(x)=\sum\limits_{i=l}^r|B_i-x|

不难发现这是个小学奥数题,显然 x=Bi+rl+12x=B_{i+\lfloor\frac{r-l+1}{2}\rfloor} 即最中间时 f(x)f(x) 是最小的,那么只要判断 f(Bi+rl+12)f(B_{i+\lfloor\frac{r-l+1}{2}\rfloor}) 小于等于 kk 即可。