OerUUU

分类

题解(2)

/ 注册

全部文章（共2篇）

【每日一题】滑动窗口（单调队列）

滑动窗口时单调队列的经典问题。时间复杂度和空间复杂度都是o（n）。单调队列即，队列中保存的值是有单调性的。实现原理类似双指针。用head指针代表对首，tail代表队尾，head > tail 即队列为空。当窗体大小大于k时，head++，即q[head]+k-1 < i.当a[i]比队尾...

每日一题单调队列

2020-04-05

1 639

【每日一题】城市网络（倍增）

题意：给你以1为根的树，问u到v有多少个节点，权值严格大于路径上所有节点的权值和w。保证v在u到根节点的路径上。首先我们考虑普通的解法，对于每一次询问，dfs从u节点到v节点，保存前缀最大值，那么当搜到的这个节点的权值大于前缀最大值时，答案加一，这样做的时间复杂度是o(nq)code: #inclu...

每日一题倍增

2020-04-05

1 671