BZOJ5173 [Jsoi2014]矩形并
BZOJ分析考虑对于每个矩形，求出其它矩形与它的交的面积之和。我们把其它矩形都加上 $1$，然后统计该矩形内的和即可。进一步可以得到这样一个做法：首先把所有矩形都加上 $1$，然后对于每个矩形统计它内部的和，减去它的面积即为所求。最后加起来除以 $n(n-1)$ 即为答案。那么问题就在于怎么支持矩形加、矩形求和了。有一个在线的做法是二维树状数组，但空间无法承受。因此可以考虑离线，用扫描线替代...
标签 扫描线 下的文章
- 首页
- 扫描线
CF903G Yet Another Maxflow Problem
CodeforcesLuogu分析最大流似乎不太好求，可以考虑求最小割。考虑给出的图的最小割的形态。容易发现我们只会割掉至多一条 $A$ 边、至多一条 $B$ 边。假设我们割掉了 $(A_u,A_{u+1})$ 和 $(B_v,B_{v+1})$，则我们还应割掉所有满足 $i\leq u,j>v$ 的边 $(A_i,B_j)$。假设 $(A_i,A_{i+1})$ 的边权为 $a_i$...
洛谷5302 [GXOI/GZOI2019]特技飞行
LuoguBZOJLOJ分析首先考虑怎么求出所有交点。注意到 $a$ 与 $b$ 有交（假设 $y_{a,0}<y_{b,0}$ ）当且仅当 $y_{a,1}>y_{b,1}$ 。那么可以用 $\mathrm{set}$ 来维护 $y_{x,1}$ ，然后暴力求出所有交点。因为交点个数 $\leq 500000$ ，所以可以过。容易发现 $a,b$ 的贡献和 $c$ 的贡献是独立...
洛谷3722 [HNOI2017]影魔
LuoguBZOJ分析对所有询问离线处理。首先用单调栈处理出每个点左右最近的比它大的数，分别记为 $L_i$ 和 $R_i$。显然 $[L_i,R_i]$ 有 $p_1$ 的贡献；左端点在 $[L_i+1,i-1]$ 之间，右端点在 $R_i$ 的区间有 $p_2$ 的贡献；左端点在 $L_i$ ，右端点在 $[i+1,R_i-1]$ 之间的的区间有 $p_2$ 的贡献。于是离线扫描：对于第...
洛谷3242 [HNOI2015]接水果
Luogu分析神仙题。前置知识：路径的包含关系设 $st[u]$ 表示 $u$ 的$\mathrm{dfs}$序， $ed[u]$ 表示 $u$ 的子树中最大的 $st[u]$。假设 $(u,v)$ 是一个盘子的两端， $(a,b)$ 是一个水果的两端，并且 $(a,b)$ 包含 $(u,v)$ ，分两种情况讨论：$u$ 和 $v$ 都不是 $\mathrm{LCA}$此时 $a$ 在 $u...
POJ1151 Atlantis
POJ分析扫描线板子？线段树维护一下总覆盖长度就行了。然而这东西不是很好维护，细节见代码。代码#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> ...
洛谷1502 窗口的星星
LuoguPOJ分析可以把星星往右上扩张，形成一个把窗户的右上角放在这个区域中就可以看到这个星星的矩形。设星星坐标为$(x,y)$，则这个矩形的右上角为$(x+w-1,y+h-1)$。这样可以保证边界不算。然后就可以用扫描线做。需要支持区间修改和区间最大值。每条扫描线就是$(x,y,y+h-1,l)$和$(x+w,y,y+h-1,-l)$。一些要注意的地方都写在代码里了。代码#include...