二手房公司如何做网站,宣传渠道有哪些,凡客诚品是什么牌子,帝国cms怎么做电影网站扫描线介绍#xff1a;OI-Wiki
【简单】一维扫描线#xff08;差分优化#xff09;
网上一维扫描线很少有人讲#xff0c;可能认为它太简单了吧#xff0c;也可能认为这应该算在差分里#xff08;事实上讲差分的文章里也几乎没有扫描线的影子#xff09;。但我认为OI-Wiki
【简单】一维扫描线差分优化
网上一维扫描线很少有人讲可能认为它太简单了吧也可能认为这应该算在差分里事实上讲差分的文章里也几乎没有扫描线的影子。但我认为一维扫描线是十分重要、也是十分套路的学过和没学过的差距很明显。希望大家认真学习。
例1
有n个点m组[ai,bi)求所有m个区间重叠的部分有多少个位置。其中m1e6,0aibin1e9
可以用扫描线思想。
扫描线可以看作是差分的优化差分处理对a[s]~a[t]中的元素1的方法d[s]1, d[t1]-1 但差分求值需要遍历整个d数组时间、空间复杂度为O(n)n为被修改数组的长度 如果长度太长比如1e9就会空间过大超时
这时就可以上扫描线其核心思想就是把差分在数组上的操作抽象成对数轴上若干个点的操作 例如差分方法d[s]1,d[t1]-1 扫描线方法在数组尾部插入 {s,1} {t1,-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位置上而不是t1}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 n n 个点 m m m 个修改每次修改都对[l,r]区间内的每个点1。1n,l,r1e9 1m1e6 1a[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;
}【困难】二维扫描线计算几何
先咕一下等会了再补 https://blog.csdn.net/Zz_0913/article/details/135128515
End
感谢大家的观看拜拜ヾ(•ω•)o
推销个人洛谷账号ylch洛谷博客YLCHUP
