题目大意

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

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

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

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

题目大意

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

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

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

题目大意

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

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

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

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

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

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

提交地址: 洛谷P3380 二逼平衡树

怎么2700的题这么简单啊QAQ

莫队+$bitset$优化

前言

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

link-cut tree 板子题

莫队好题