10月2日二分与倍增

二分通常分为两类:二分查找和二分答案.

T1

problem

给出一个数列$a[1…n]$,现在有m个询问,每次询问比x大的最小的$a[i]$的值.

ans

离线:数列和询问都排序,然后扫一遍.

在线:排序,二分查找.

T2

problem

定义一个区间的值为其众数出现的次数.先给出一个数列$a[1…n]$,求在所有区间的值中,第k大的值是多少.区间大小为1的不计.

ans

设答案为ans,则$ans\in [2,n]$.设函数$f[mid]$为值$\le mid$的a有多少个,题目要求$f(ans)>=K$且$ans$最大.然而这个函数是单调不增的.所以我们通过二分答案来找到ans.

关键是怎么求f的值.

小总结

T3

problem

[NOIP2011]聪明的质检员

ans

可以发现w越大,y越小.此时$y=f(w)$是一个单调不上升函数.因此我们用二分法求出函数的零点即可.

T4

problem

[NOIP2015]跳石头

ans

二分跳跃距离,然后扫一遍如果两块石头之间的距离小于mid的话就移走一块.最后比较移走石头的数与m的大小.

T5

problem

对于一个字符串,询问q次,每次询问$[l,r]$内最长回文串的长度.$n,q\le 1e5$.

ans

T6

problem

一个$n\times m$的网格图,其中有的格子有障碍,有的没有.有T个询问,每次询问一个子矩阵,查询该子矩阵内边长最大的没有障碍的正方形的边长

ans

二维ST表(跪).

扩展:$\Theta(1)LCA$

如图,如果我们想要求出6和5的LCA,我们可以看到在深度序中2和5中间深度最小的是2,所以LCA是2.这个过程需要一次DFS和一个ST表.