Блог пользователя hphucvn

Автор hphucvn, история, 19 месяцев назад, По-английски

In original problem 1175F - The Number of Subpermutations, it is required to count the number of subpermutations that consist number from 1 to r — l + 1, each appear exactly once

I managed to solve it using two pointers, expanding from position i whereas a[i] = 1

How do I count number of subpermutations, starting from x to x + r — l, for example : [1, 3, 2] and [2, 4, 3] also counts. Also, it would be great if someone can find the submission link for this problem. Thanks for helping me.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
19 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +3 Проголосовать: не нравится

This is a classic problem which can be solved using lazy segment tree and monostack. Here is the original problem:

526F - Pudding Monsters

The basic idea is that you may reformulate ur restrictions for a segment $$$[l,r)$$$ to:

$$$\max_{i=l}^{r-1}a_i-\min_{i=l}^{r-1}a_i=r-l$$$

Then each of these four terms can be maintained while sweeplining and a monostack, with a lazy segtree that supports range set, range addition, and querying range minimum counts.

You can refer to my code for imple details: 313322006