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.
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:
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