线段树

洛谷题库 P8868 [NOIP2022] 比赛

本文记号可能稍显凌乱,但都能在题面或者前文中找到定义。

部分分

20 pts\text{20 pts}n,Q3000n,Q\leq 3000

考虑枚举所有 O(n2)\newcommand\bigO{\operatorname{O}}\bigO(n^2) 个区间,预先计算它们本身的答案。记 ga(l,r)=max{ailir}gb(l,r)=max{bilir}\begin{aligned}g_a(l,r)&=\max\{a_i\mid l\leq i\leq r\}\\g_b(l,r)&=\max\{b_i\mid l\leq i\leq r\}\end{aligned},则做前缀和 s(l,r)=i=lrga(l,i)gb(l,i)s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i),对于询问 [ql,qr][\text{ql},\text{qr}] 只需回答 i=qlqrs(i,qr)\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr}) 即可。

n,Qn, Q 同阶,时空复杂度 O(n2)\bigO(n^2)(更多…)

More
  • 2022年12月8日

仍然是中规中矩的一场模拟赛。前两题正解,第三题暴力,第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边,若是则无解,若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路:两球相撞调转方向时,我们不认为是球本身转向,而认为两球仍然保持原方向运动,而其编号交换(更多…)

More
  • 2022年11月20日

44 道题全部只会暴力。还不如直接发下来当练习做呢,省得在场上罚坐三小时浪费时间。

简略题解

A – 神灵庙

观察发现:

  • 当树的形态确定时,我们总是将权值更大的节点安插到深度更小的叶子上。可以将 aa 降序排序后逐层填写。
  • 一个节点只可能有 00 个或者 22 个儿子。如果只有 11 个儿子,显然可将该节点删除而整棵子树全部向上平移。

f(d,i,c1,c2)f(d,i,c_1,c_2) 表示“现在位于第 dd 层(此处“层”指的是节点实际深度)。已经填写好了 a1,a2,,aia_1,a_2,\cdots,a_i,且第 dd 层共 c1c_1 个空置(非叶子)节点,第 d1d-1 层有 c2c_2 个此类节点”。那么两层的每一空置节点,均会有一个第 d+1d+1 层的儿子。枚举“下一层要填写 kk 个元素”,有转移 f(d+1,i+k,c1+c2k,c1)f(d,i,c1,c2)+(j=i+1i+kaj)(d+1)f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1) (更多…)

More
  • 2022年11月18日

Atcoder ARC149D – Simultaneous Sugoroku

官方题解做法是线性的,在此不再赘述。

考虑对于纸片 X=1,2,,max{Xi}X=1,2,\cdots,\max\{X_i\} 分别计算答案。每次暴力枚举显然不可取,但假若我们知晓对于 XX,在 i=0,1,,Mi=0,1,\cdots,M 次操作以后纸片在数轴上的坐标 x0=X,x1,,xmx_0=X,x_1,\cdots,x_m,其中 pos\text{pos} 是最小的取到 xpos=1x_\text{pos}=-1 的位置,则对于 x0=X=X+1{x_0}’=X’=X+1

  • 如果 pos\text{pos} 不存在,则所有坐标整体向数轴正半轴平移 11 单位;
  • 否则,pos\text{pos} 就将是起始点为 XX’ 的纸片首次到达 00 点的位置,也即题目所求。所有小于 pos\text{pos} 的坐标仍向正半轴平移 11 单位;而 pos\geq \text{pos} 的坐标,由于偏移量 DiD_i 符号翻转,则有 xixi1=(xixi1){x_i}’-{x_{i-1}}’=-(x_i-x_{i-1})。依次考虑每一坐标,就会得到 xi=1xi,posim{x_i}’=1-x_i,\forall \text{pos}\leq i\leq m。 (这里认为当 xpos=0x_\text{pos}=0 时仍然继续执行操作。维护 pos\geq\text{pos} 的坐标位置是为了计算 X>XX”>X’ 的答案。)

这是可以用区间树维护的:我们想要快速求出全局非正数最大值以及首次取到该最大值的位置,同时支持全局加 11、后缀所有数符号翻转×1\times -1)。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置,采用延迟标记更新(两种操作对于前述信息是具有结合律的,形成幺半群)即可。

时间复杂度 O(max{Xi}logM)\operatorname{O}(\max\{X_i\}\log M),常数一般。

Submission #36155560 (更多…)

More
  • 2022年11月2日

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 xx 的子树全部染白”的操作,应当怎样处理?

题目所给操作可以这样转述:令 xx 为本次染色操作的节点。若 xx 为白色,则立刻染黑并退出;否则我们找到其子树中的,与 xx 相连的黑色连通块,则对于每个连通块底部节点,若其不是叶子节点,我们将其儿子染黑。

由于本题的树没有特殊性质,且将来加入回退操作,故而难以维护整个连通块以及其叶子节点。因此,我们可以从“在何种情况下,节点 xx 被染黑”的方向考虑。

显然,只有从在 xx 到根的路径上的节点开始的染色操作,才可能波及到 xx。假如最终 xx 被染黑的一瞬,它被包含在了以 comprt\text{comprt} 为根的连通块中。令链 comprt,x\langle\text{comprt}, x\rangle{x1,x2,,xn},x1=comprt,xn=x\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x,那么自然想到,一种一定合法的染色序列是 {y1,y2,,yn}\{y_1,y_2,\cdots,y_n\},其中有 k[1,n]Z,yk{x1,,xk}\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\},也即我们每一步都在该连通块内部,并将连通块的最大深度推进一层

这种序列确实合法(它是充分条件),但这真的是 xx 被染黑的必要条件么? (更多…)

More
  • 2022年7月16日

一道让我做得相当高兴的题目。

原题链接 (这是付费比赛。)

题意简述

给定长度为 nn 的序列 aa。定义函数 f(S)=TSF2(sTs)f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s),也即“对于 SS 的所有子集,求 F(子集所有元素之和)的平方F(\text{子集所有元素之和})\text{的平方} 之和”。其中 F(x)F(x) 为斐波那契数列的第 xx 项。有F(0)=0,F(1)=1,F(x)=F(x1)+F(x2)(x>1)F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)

你需要支持以下操作,操作总数为 mm

1 x y:将 axa_x 修改为 yy

2 l r:输出 i=lrj=irf({ai,ai+1,,aj})\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\}),对 998244353998244353 取模。

数据范围:对于 \text{50%} 的数据,有 n,m100n,m\leq 100;对于 \text{70%} 的数据,有 n,m1000n,m\leq 1000;对于 \text{100%} 的数据,有 n,m105,ai105n,m\leq 10^5, a_i \leq 10^5

(更多…)

More
  • 2022年6月20日

一场相当有收获的比赛。比赛链接

A – 石老板举世无双

解法一

尝试观察规律。我们发现,在完成ss次操作以后,左端点的可能取值为xa+(2sx)b2s,x[1,2s]\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s],右端点的可能取值为xa+(2sx)b2s,x[0,2s)\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)。假如现在我们达到最终状态,其l=(x+1)a+(2sx1)b2s,r=xa+(2sx)b2sl=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}。那么,在xx的二进制表示中,如果从高到底pos\mathrm{pos}位为11,则在第pos\mathrm{pos}轮中,有check (mid) == 0,向右区间递归;否则向左区间递归。这是很容易解释的:若向右递归,则右端点不变。而在下一层,右端点表示中a,ba, b的所有系数乘22,所以体现为二进制位末尾添一个00。反之,就变成(x+(x+1))/2(x+(x+1))/2,在下一层中体现为2x+12x+1。如果其有popc(x)\operatorname{popc}(x)位为11,则到达该状态的概率为p0popc(x)p1spopc(x)p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}

s=3s=3时的状态l=3a+5b8,r=2a+6b8l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}为例。22的三位二进制表示为0b010\text{0b010},则推断出在前三轮分别向右、左、右区间递归,到达其的概率为p0p12p_0p_1^2(更多…)

More
  • 2022年5月17日

CodeForces Round #755 Div.2 F / Div.1 D Serious Business

此题整整困了我一天半,耗费了好几张草稿纸。实在走投无路,翻看题解,却发现正解曾经近在咫尺。有必要稍作整理。

考虑DP。

错误转移1

这道题与清理班次(《算法竞赛进阶指南》上的一道例题)过于相似,都是“给定一些段落[lp,rp][l_p, r_p],选择其中一些完整覆盖[l0,r0][l_0,r_0],求最小花费”的形式。记上述花费为f(l0,r0)f(l_0, r_0)。但本题与原题不一样之处在于其起点和终点是任意给定的。我的第一反应是枚举在x2x_2位置从第22行转到第33行,利用数据结构维护所有x1x2x_1\leq x_2,在x1x_1转移到第二行,解锁到达x2x_2的最小代价。对于各行前缀和,我们可以利用线段树或树状数组维护。同时我们也知道可以利用数据结构优化在O(nlogn)\mathrm{O}(n \log n)的时间内,计算出对于一个固定的起点l0l_0,所有f(l0,r0),r0[l0,n],p,rp=r0f(l_0, r_0), r_0 \in [l_0, n], \exists p, r_p=r_0的值。 (更多…)

More
  • 2022年3月8日

是的,又是一道考试时想出正解没有打出来的题目

货物分组 – 牛客网

根据题意,我们很容易想到一个朴素的类区间DP——令dp(i,j)dp(i, j)表示现在将第ii件货物划分到第jj箱中,且作为箱内的最后一件货物,所需最小花费。容易写出转移:dp(i,j)=mink[0,i)p=k+1iapWdp(k,j1)+p=k+1iap+极差{att[k+1,i]}dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\},初值有dp(0,0)=0dp(0, 0) = 0,应求得minj[1,n]dp(n,j)\min\limits_{j \in [1, n]} dp(n, j)

(更多…)

More
  • 2021年10月22日