题目大意

给定一颗有根树,根为 $1$ ,有以下两种操作:

  1. 标记操作:对某个结点打上标记。(在最开始,只有结点 $1$ 有标记,其他结点均无标记,而且对于某个结点,可以打多次标记。)

  2. 询问操作:询问某个结点最近的一个打了标记的祖先。(这个结点本身也算自己的祖先)

$1 \leq n, q \leq 10^5 $

CF504E Misha and LCP on Tree

题目大意

给你一棵有$n$个节点的树,每个节点上有一个字符$c$。

有$m$次询问,每次询问$a\sim b$路径上的字符串和$c \sim d$路径上的字符串的最长公共前缀$\texttt{(LCP)}$

$n \leq 3 \times 10^5,m \leq 10^6$

CF1285D Dr. Evil Underscores

题目大意

你有一个数组${a_n}$,求一个数$x$ ,满足$\max{a_i \oplus x}$最小,输出这个最小值

洛谷4314 cpu监控

首先我们可以想到一个显而易见的思路:每个节点维护$\mathrm{add,set}$的$tag$,维护最大值$max$和历史最大值$Max$,然后像正常的线段树一样维护

然后你惊讶的发现你只拿到二十分(只有$Q$的部分分)

为什么呢?我们发现有些$tag$,他还没有来得及被更新就被覆盖了..而这些$tag$本来能改变世界更新答案

所以我们可以维护两个$tag$:$\mathrm{Add,Set}$表示该节点从上次下放到目前的最大$add$和$set$值

然后我们就可以快乐的用这些$tag$来维护答案了

CF86D Powerful array

怎么2700的题这么简单啊QAQ

莫队+$bitset$优化

「算法笔记」 莫队

前言

莫队,可是传说中能够解决所有离线区间问题的神奇算法

洛谷 P3950 部落冲突

link-cut tree 板子题

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×