JOISC2019 简要题解
官网AtCoderLOJ試験 / Examination三维偏序板子，CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
标签 扫描线 下的文章
- 首页
- 扫描线
LOJ535 「LibreOJ Round #6」花火
LOJ分析如果只能用操作 $1$，根据某个经典结论答案就是逆序对数。于是很容易想到 $\mathcal{O}(n^3\log n)$ 的暴力：枚举操作 $2$ 交换了哪两个位置，然后求逆序对即可。考虑优化。因为每次只交换了两个位置，所以没有必要整个重新求一遍逆序对。假设交换了 $i$ 和 $j$，原来的逆序对数是 $A$，那么交换后的逆序对数 $A'$ 为讨论一下：当 $p_i<p_j...
BZOJ5173 [Jsoi2014]矩形并
BZOJ分析考虑对于每个矩形，求出其它矩形与它的交的面积之和。我们把其它矩形都加上 $1$，然后统计该矩形内的和即可。进一步可以得到这样一个做法：首先把所有矩形都加上 $1$，然后对于每个矩形统计它内部的和，减去它的面积即为所求。最后加起来除以 $n(n-1)$ 即为答案。那么问题就在于怎么支持矩形加、矩形求和了。有一个在线的做法是二维树状数组，但空间无法承受。因此可以考虑离线，用扫描线替代...
洛谷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...