2019牛客多校第一场A – Equivalent Prefixes

题目链接:2019牛客多校第一场A

让$a_i$和$b_i$同时进入单调队列,单调队列保存元素的值和下标,如果进队/出队的时候,$a_i$所在的单调队列和$b_i$所在的单调队列的下标值是一样的,那么就是OK的,直到找到状态不一样的位置,那么答案为它的前一个。渐进时间复杂度$O(n)$。

 

说点什么

avatar
50
  Subscribe  
提醒