ZigZagK的博客
[单调栈+扫描线+线段树]2020 ICPC 小米 网络选拔赛热身赛 H【Equivalent Prefixes】题解
题目概述Equivalent Prefixes解题报告首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间( $a_i$ 最小的区间),还有 $[LB_i,RB_...
[离散+线段树分治+并查集按秩合并]2020 ICPC 小米 网络选拔赛热身赛 E【Explorer】题解
题目概述有 $m$ 条边,每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过,如果人数 $x$ 能够从 $1$ 到 $n$ 则可行,求可行的 $x$ 的数量。解题...
[主席树求区间mex]Codeforces1436E【Complicated Computations】题解
题目概述CF1436E解题报告呜呜呜,忘了区间mex可以用主席树做了QAQ。开 $n$ 个权值主席树,第 $i$ 棵树记录 $1\sim i$ 中 $x$ 最后一次出现的位置 $pos_x$ 。...
[扫描线+线段树]Codeforces1435C【Perform Easily】题解
题目概述CF1435C解题报告将 $a$ 排序,令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ,然后对于每个 $i$ 我们采用第一个 $\ge x$ 的 $B_{i,j}$ ,...
[离线+线段树]Codeforces1405E【Fixed Point Removal】题解
题目概述CF1405E解题报告显然有贪心:当有多个可以删除的元素同时存在时,先删除后面的,因为删后面的不影响前面。既然如此,我们从左往右考虑一个位置能否被删除。对于一个位置 $i$ ,如果前面已...
[线段树]ACL Beginner Contest E【Replace Digits】题解
题目概述ACL Beginner Contest E解题报告不知道各位数学课上有没有求过这个数列的通项公式……
[DP+单调栈+线段树动态开点]Codeforces1407D【Discrete Centrifugal Jumps】题解
题目概述有 $n$ 个建筑物,高度 $h_i$ 。要从 $1$ 跳到 $n$ ,求最少跳跃步数。$i\to j$ 的跳跃要求:$i+1=j$$\max(h_{i + 1}, \ldots, h_...
[主席树+哈希]HackerRank(101 Hack 49)【Sorting Lists】题解
题目概述有 $n$ 条线段 $(a_i,b_i)$ ,定义 $C(i)$ 表示包含 $i+{1\over 2}$ 的有序线段列表,求字典序第 $K$ 小的 $C(i)$(相同列表不重复计算)。解...
[单调栈+线段树]HackerRank(101 Hack 50)【Boxes for Toys】题解
题目概述有 $n$ 个箱子,每个箱子的长宽高为 $(a_i,b_i,c_i)$(可以任意旋转),把 $[l,r]$ 的箱子装入一个大箱子需要满足区间内任意的箱子三维都小于等于大箱子,求所有区间最...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内,所以可以把值域也分块,这样移动指针就不需要带 $l...