夏晓光(loveJY)的博客

被迫营业

按理说这个博客是不应该有算法专讲的?

扫描线就是字面意思,一条从1到n扫过去,差分一切的线qwq

直接上例题

矩阵并面积和

线段树维护出现次数和当前出现长度

然后把每条竖着的线段离线下来按照x坐标排序,对于同一矩阵,x小的为+,反之为-

[模板]扫描线

固定大小矩阵最大值

把一个点的权值变成考虑右上角在哪个范围能够覆盖到这个点,从而得到一个右上角集合的矩形

然后扫描线变成区间加,区间查询最大值

窗口的星星

NOI online T2

扫描线变成考虑右端点在i的所有区间的贡献

然后线段树维护后缀平方和+HH的项链

七彩EI下的愿望花环

这个题我们假设增量是出现的颜色种类数K,也就是说问你所有区间中权值和+种类数K的最大区间的值是什么

还是扫描线,线段树维护一下从i到r的区间和

颜色种类还是HH的项链,用pre[a[i]]

每次把$1 到 pre[a[i]]$的加上a[i],把$pre[i]+1~i$的加上a[i]+K

答案就是每次的全局最大值

区间mex

考虑离线,然后权值线段树维护值为i的最后出现时间

对于所有右端点在r的询问,二分一个最小的k,使得$val[k]<l$

k就是答案,在线可以可持久化线段树

矩阵周长

扫描线,矩阵周长可以拆成两部分,从上到下和从左到右扫描线分别扫一遍

然后线段树维护这个位置出现次数以及出现了的长度,和直线矩阵并面积一样

常数*2警告?

Iron man