用户工具

站点工具


2020-2021:teams:legal_string:lgwza:扫描线问题

这是本文档旧的修订版!


扫描线问题

例 1

题意

求 $n$ 个矩形的面积并

题解

此问题可抽象出一个问题模型:

给一初始全 0 的序列 $\{a_i\}_{i=1}^n$,每次操作如下:给定区间 $[l,r]$,令 $a_i=a_i+1,\forall i\in [l,r]$ 或 $a_i=a_i-1,\forall i\in [l,r]$,修改后立即询问 $\#\{a_i|a_i>0,i\in[1,n]\}$,保证任一修改后 $a_i\ge 0,\forall i\in[1,n]$

2020-2021/teams/legal_string/lgwza/扫描线问题.1631848413.txt.gz · 最后更改: 2021/09/17 11:13 由 lgwza