A range problem

Revision en2, by nhphuc, 2025-04-26 14:12:12

Summary: Given an array $$$A$$$ with $$$N$$$ elements. Find the largest continous subbarray $$$(l,\ r)$$$ of $$$A$$$ that: $$$max(A_l,\ A_{l + 1},\ ...,\ A_r)\ \vdots\ min(A_l,\ A_{l + 1},\ ...,\ A_r)$$$. Print the value $$$r - l + 1$$$. constraints: $$$n\leq 6\times 10^5,\ a_i\leq 10^5\ forall\ 1\leq i\leq n$$$.

Subtasks:

  • $$$n\leq 500$$$ and $$$n\leq 5000$$$: for $$$O(n^2)$$$.

  • $$$a_1\leq a_2\leq ...\leq a_n$$$: for dp $$$O(n\ log\ n)$$$.

  • $$$a_i\leq 1000$$$: dont know how to do.

  • $$$n\leq 10^5$$$: dont know how to do.

  • No additional constraints: dont know how to do.

Please help me with this problem, thanks for your help and attention. Have a good day !

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English nhphuc 2025-04-26 14:12:58 24 Tiny change: 'i\leq 10^5\\ forall\ 1\leq i\leq n$.\n\nSubt' -> 'i\leq 10^5$.\n\nSubt'
en2 English nhphuc 2025-04-26 14:12:12 355 (published)
en1 English nhphuc 2025-04-26 14:07:57 298 Initial revision (saved to drafts)