ZigZagK的博客
[单调栈+扫描线+线段树]2020 ICPC 小米 网络选拔赛热身赛 H【Equivalent Prefixes】题解
题目概述Equivalent Prefixes解题报告首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间( $a_i$ 最小的区间),还有 $[LB_i,RB_...
[扫描线+线段树]Codeforces1435C【Perform Easily】题解
题目概述CF1435C解题报告将 $a$ 排序,令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ,然后对于每个 $i$ 我们采用第一个 $\ge x$ 的 $B_{i,j}$ ,...
[扫描线]Codeforces853C【Boredom】题解
题目概述CF853C解题报告直接求很麻烦,我们求不满足的个数。对于询问的矩形 $A$ ,我们划分出八个区域: | 0 | 1 | 2 | ------------- | 3 | A | 4 ...
[离线+扫描线+LCT]BZOJ4573(Zjoi2016)【大森林】题解
题目概述有 $n$ 棵树和 $m$ 个操作,操作有:1.在 $[L,R]$ 树当前根的后面加一个点。2.把 $[L,R]$ 树的根改为 $x$ 。3.询问第 $x$ 树中 $A$ 到 $B$ 的...
[扫描线+线段树]LOJ6276【果树】题解
题目概述一棵 $n$ 个节点的树,每个节点有颜色,求路径上没有相同颜色的路径个数,每种颜色出现次数不超过 $20$ 。解题报告填联赛前的坑,模拟考的时候我疯狂想容斥,我都想到用正解做链了却没想到...
[扫描线+笛卡尔树+随机]BZOJ2658(Zjoi2012)【小蓝的好友(mrx)】题解
题目概述有一个 $R\times C$ 的网格,其中 $n$ 个格子有资源点,问至少有一个资源点的子网格个数。解题报告万年神坑。先补集转化,那么就是用总方案数减去一个资源点都没有的子网格个数,把...