【2024最新】C++扫描线算法介绍+实战例题

扫描线介绍：OI-Wiki

【简单】一维扫描线（差分优化）

网上一维扫描线很少有人讲，可能认为它太简单了吧，也可能认为这应该算在差分里（事实上讲差分的文章里也几乎没有扫描线的影子）。但我认为，一维扫描线是十分重要、也是十分套路的，学过和没学过的差距很明显。希望大家认真学习。

例1

有n个点，m组[ai,bi)，求所有m个区间重叠的部分有多少个位置。其中m<=1e6,0<=ai<bi<=n<=1e9

可以用扫描线思想。

扫描线可以看作是差分的优化，差分处理对a[s]~a[t]中的元素+1的方法：d[s]+=1, d[t+1]-=1
但差分求值需要遍历整个d数组，时间、空间复杂度为O(n)，n为被修改数组的长度
如果长度太长（比如1e9），就会空间过大+超时

这时就可以上扫描线，其核心思想就是把差分在数组上的操作抽象成对数轴上若干个点的操作
例如：差分方法：d[s]+=1,d[t+1]-=1；扫描线方法：在数组尾部插入 {s,+1} {t+1,-1}

这样只要对存储点修改的数组进行遍历，再用累加变量累加修改值，就能实时得到当前点的值
同时，当前修改点和上一个修改点之间的所有数组元素，其值都是上一个修改点位置的累加变量
这样时间、空间复杂度都为O(m)，m为修改点的个数，肯定能过

扫描线的注意事项：
1.存储点修改的数组，用vector方便，但有常数过大而超时的风险。建议在m比较大的时候使用普通数组

2.存储所有修改点之后一定要按照修改位置从小到大排序，不然就乱了

3.排序后还要处理同一个点多次修改的重复问题，有三种主流的解决方案：
1）在遍历所有点时，先对它和它之后所有修改下标一致的点进行合并，再计算。这是比较稳妥的方法

2）在求最值等一些特殊的题目中（比如例1），重复累加并不影响操作，可以根据排序让它只有在同一个点都累加完后，才出现对答案有贡献的值
比如，求最大值。可以排序时先按照下标升序排序，再把-1操作排在+1前面，这样遍历时先减再加，不会影响最大值的求解。

3）使用万能的map。map就像一个桶数组一样，可以很方便地把所有点的修改都累加到一块去。还能自动按照键升序排序，绝对是为扫描线量身定做的梦想中的容器！
但这样虽然方便，会有因常数过大而超时的风险（map理论复杂度为O(nlogn)，但这个log很大）

Code：

#include <bits/stdc++.h>
using namespace std;struct Node{int pos, add; // 位置pos，贡献addfriend bool operator < (Node p1, Node p2){ // 先按照位置升序排序，再按照贡献升序排序（减法要排在加法前面，不然会导致先加得大了，然后求max时答案出错）if(p1.pos != p2.pos) return p1.pos < p2.pos;return p1.add < p2.add;}
};void solve()
{int n;cin >> n;vector <Node> A;for(int i = 0, b, t; i < n; i ++){cin >> b >> t;A.push_back({b, 1});A.push_back({t, -1}); // 注意大炮的范围是[b,t)，所以差分的-1应该在t位置上，而不是t+1}sort(A.begin(), A.end());int ans = 1, d = 0; // ans是答案，d是差分值for(auto it : A){d += it.add;ans = max(ans, d);}cout << ans << "\n";
}signed main()
{ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);solve();return 0;
}

例2

有 $n$ 个点， $m$ 个修改，每次修改都对[l,r]区间内的每个点+1。1<=n,l,r<=1e9 1<=m<=1e6 1<=a[i]<=1e6
求 Σcnt[i]*a[i] 其中cnt[i]表示点的值为i的个数，a[i]表示每个值为i的点对答案的贡献。

这道题需要求区间修改后n个点中每一个值的个数。
记得前面说过“同时，当前修改点和上一个修改点之间的所有数组元素，其值都是上一个修改点位置的累加变量”。

由此，能知道两个修改点之间的所有点的值，又可以容易地计算出两个修改点之间差了多少个点。就可以统计cnt数组了。（具体看代码里pre变量的使用）

但这道题的难点不在于扫描线，而是出题人……
1.不能给所有变量都开long long，这样会因为常数过大而超时（因为long long占8个字节，int占四个字节，所以long long平均每次运算次数都是int的两倍）

2.如果你图方便用map存储所有的修改点，以为这样就不用考虑重复的问题了。但抱歉，出题人也会卡

在OI赛制下，很少有人能注意到上面两个坑点。码风朴实，没有那么多花里胡哨的同学反而因为不用STL而占据优势。

Code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxm = 1e6 + 5;int n, m;
int a[maxm], cnt[maxm]; // cnt:记录个数的桶数组struct Node{int p, t; // 表示p位置的修改为tfriend bool operator < (Node p1, Node p2){return p1.p < p2.p;}
};
vector <Node> d; // 差分数组void solve()
{cin >> n >> m;for(int i = 1; i <= m; i ++) cin >> a[i];for(int i = 1, l, r; i <= m; i ++){cin >> l >> r;d.push_back({l, 1}); d.push_back({r + 1, -1}); // 进行差分}sort(d.begin(), d.end()); // 排序int pre = -1; // 上一个差分的点int ans = 0; // 累加变量for(int i = 0; i < d.size(); i ++){int pos = i;while(d[i].p == d[i + 1].p){ // 把同一个位置的所有修改都累加起来，这样便于统计答案d[pos].t += d[i + 1].t;++ i;}if(pre != -1){cnt[ans] += (d[pos].p - 1) - pre + 1; // 累加的答案区间是[pre,d[].p)}ans += d[pos].t; // 累加pre = d[pos].p; // 记录前一个端点}ll tot = 0;for(int i = 1; i <= 1e6; i ++){tot += 1LL * a[i] * cnt[i]; // 对于不存在的，cnt[i]一定=0，其不会被记录}cout << tot << '\n';
}signed main()
{ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}