扫描线

之前写的搬一下

扫描线应该说是一种数据结构的维护思想，处理的问题经常是查询一段区间内子区间的信息，并且可以离线处理。

大致的流程是把询问离线下来，按某个东西排序，然后从 \(1\) 到 \(n\) 遍历序列，不断加上维护的信息，在某些时刻（比如到达一个询问的端点时）把对应询问的答案给搞出来，放到数组里面，接下一个询问。

刚才有个大佬回复说：扫描线本质上就是把一个维度轴当做时间轴来看，然后拿点 DS 去维护这个“时间轴”前进过程中的变化。这就很形象地解释了修改和查询一起进行的过程。这样我们边修改边查询，修改 \(n\) 次查询 \(m\) 次，复杂度 \(O((n+m)\log n)\)。

大概的代码框架，很简单：

for(int i=1,j=1;i<=n;++i){
		update();
		while(j<=m&&q[j].r==i){
			ans[q[j].id]=query();
			++j;
		}
	}

P9991 Ynoi Easy Round 2023 TEST_107

我们考虑一个极长子区间可能是长啥样的，有三种可能：

\(1.\) \([l′,r′]=[l,i]\)，满足 \(a_{i+1}=x,\forall j\in[l,i],a_j\neq x\)

\(2.\) \([l′,r′]=[i,r]\)，满足 \(a_{i-1}=x,\forall j\in[i,r],a_j\neq x\)

\(3.\) \(l′>l,r′<r\)，满足 \(a_{l′-1}=a_{r′+1}=x,\forall j\in[l′,r′],a_j\neq x\)

先考虑 \(1\)，我们记录 \(las_i\) 表示上一个 \(a_i\) 所在的位置。扫描线每扫过一个 \(i\) 就把线段树上 \(las_i\) 的位置改为 \(i\)，这样你在 \(r_j=i\) 时线段树上 \([0,l_j-1]\) 的最大值就代表 \([l_j,r_j]\) 中那个符合 \(1\) 情况的 \(i\)。\(2\) 情况只需要将整个序列倒过来，更新 \(las_i\)，同时把询问也倒过来，进行和 \(1\) 情况相同的操作就行。\(3\) 情况扫到 \(i\) 的更新就变成了把 \(las_i\) 位上变成 \((i-1)-(las_i+1)+1\)，查询就直接查 \([l_j,r_j]\) 的最大值即可。

再说一下扫描线具体是怎么扫的：我们从 \(1\) 到 \(n\) 遍历原序列，每扫到一个 \(i\) 就 update，将线段树上 \(las_i\) 位置（一般化地来说就是和 \(i\) 形成有贡献的区间的一个位置）修改为 \(i\)，表示在查询的区间包含 \(las_i\) 时 \([las_i,i]\) 这段区间是被包含的，可以产生贡献的。每扫到一个 \(r_j=i\) 时就进行查询，把答案更新到数组对应编号中，一次这样的扫描线是 \(O((n+m)\log n)\) 的。

for(int i=1,j=1;i<=n;++i){
		update(1,0,n,las[i],i); //注意这里会有-1，会涉及到0
		while(j<=m&&q[j].r==i){
			ans[q[j].id]=max(ans[q[j].id],query(1,0,n,0,q[j].l-1)-q[j].l);
			++j;
		}
	}

GSS2 - Can you answer these queries II

有参考价值的。显然不能像GSS1那样直接线段树维护前后缀最大子段和了，因为涉及到子区间，考虑能不能离线下来扫描线处理。这里有个trick：我们让线段树的每个叶节点表示以 \(i\) 为开头的最大子段和，每次在线段树上对 \([las_i+1,i]\) 加上 \(a_i\)，这样就能保证相同的数的贡献覆盖区间无交，并维护区间历史最大值。维护历史最大值是很容易感性理解的，你还需要同时维护历史最大的 tag。

P9990 Ynoi Easy Round 2023 TEST_90

因为涉及到子区间个数计数，也就是需要考虑到所有子区间。一个trick是考虑扫描线记录线段树上的历史版本和，很好感性理解，因为我们扫描线是在不断加上新的元素的贡献，相当于将区间右端点的取值范围扩展到了当前的 \(i\)，所以所有区间的答案之和就是所有历史版本之和。

然后考虑对每个数考虑他的贡献。显然他能影响到的区间和前几道题一样还是 \([las_i+1,i]\)，而他的贡献相当于是将所有区间答案的奇偶性取反。想要统计答案还需要记录每个节点上答案为 \(0/1\) 的区间个数被统计的次数，记为 \(t0,t1\)，这样每个区间的答案就是两个 tag 乘上对应答案的子区间个数。注意你每次修改都要对 \([1,n]\) 额外修改一次 t[1].t1++,t[1].ans+=t[1].sum1;，这样这个 \(t1\) 就可以下传到整颗线段树。

CF522D

扫描线板题，独立秒了欸。将 \(las[i]\) 修改成 \(i-las[i]\) 然后查区间最小值就做完了。