20.07.05

扫描线

一种思想（做题方法），不是什么有名有姓的算法。

经典例题：矩形面积并

核心：离线+排序

考虑一条平行于坐标轴的直线从下向上逐渐“扫描”到无穷远处。

注意：离散化

一些题目：

Luogu P5567 立方体覆盖 (立方体体积并)

BZOJ 2161 布娃娃

由于BZOJ已经没了，在这里稍微说一说。

题面：

有 $n$ 个布娃娃，第i个布娃娃有一个耐心值 $P[i]$ 以及一个魅力值 $C[i]$ ，并且还有能够忍受的耐心值的上限 $R[i]$ 以及下限 $L[i]$ 。当一个布娃娃 $j$ 满足 $L[j]<=P[i]$ 并且 $P[i]<=R[j]$，那么布娃娃 $j$ 喜欢布娃娃 $i$。雨荨还发现，一个布娃娃有可能喜欢它自己。每个布娃娃心中都有一个谜团，具体来说就是：第 $i$ 个布娃娃想知道喜欢它的布娃娃中，魅力值第 $i$ 大的布娃娃的魅力值是多少，并且称这个布娃娃的谜团答案为这个魅力值的大小，如果不存在，那么这个布娃娃的谜团答案为 $0$。求所有布娃娃谜团答案的和除以 $19921228$ 的余数是多少。

$n<=10^5$

把出题人写的说人话的题面抽象成简单清晰的模型是很重要的能力。

题目等价于在一维数轴上给一些线段和一些点，线段有权值。求覆盖某个点的所有线段中权值第 $k$ 大的是多少。

权值线段树+扫描线即可。

总结：
离线拆分，数据结构维护，可以结合数据结构的嵌套。

线性基：

具体的原理和证明需要高等代数知识，在此只能介绍性质和简单应用。

线性基：线性空间的一组基

什么是线性空间：
在一个集合中定义了两种运算，加法和数乘。
这两种运算满足交换律和结合律。定义的运算和集合构成了一个线性空间。
详细的定义会复杂的多，感性认识一下好了（
什么是基：
感性的认识，“代表”某一线性空间的元素集合。

举个例子，$R^2$是一个线性空间。

还有什么？

无符号整数集上的异或运算构成一个线性空间。（异或空间）
这是算法竞赛中线性基的最主要应用。

线性基有什么性质：

可以对标$R^2$具有的性质。

1. 原集合中的任意一个数都可以由线性基内的一些元素异或得到。相反也成立。
2. 线性基内任意（非零）个数的异或和不为零。
3. 线性基内的元素个数在满足上述条件下是最少的。

线性基以增量法构建，且仅支持插入，不支持删除。

int p[32];
void ins(int x)
{
    for(int i=31;i>=0;i--)
    if((x>>i)&1)
    {
        if(!p[i])
        {
            p[i]=x;
            return ;
        }
        x^=p[i];
    }
}

相当于对每一位存了一个“代表元素”，每次消掉最高位。若消为了零，则说明这个数一定已经可以被线性基内的元素表示，否则需要存储这个数。

关于线性基具体的应用性质，常常和“贪心”紧密相连。

全局最小元素：即最小的$p_i$。
需要特判“0”

全局最大元素：从高位向低位贪心即可。

Luogu P4570 [BJWC2011]元素

权值为1的情况：

更进一步的【严格】证明需要拟阵的知识，这个更复杂了。

“实质”：高斯消元

Luogu P3265 [JLOI2015]装备购买

$R^m$ 上的线性基