MdOI

题目描述 给你两个长度为 \(n\) 的序列 \(a\) 和 \(b\)，让你选 \(n\) 个 \(c_i \in [a_i,b_i]\)，使得 \(\frac{1}{n} \sum_{i=1}^n (c_i- \overline c)^2\) 最大。 具体思路 首先我们从方差的定义出发，方差代表 ......

$$\large(\sum\limits_{i=1}^n |s_i|)-(\sum\limits_{i=1}^{n-1} |s_{p_i}\bigcap s_{p_{i+1}}|)=|\bigcup\limits_{i=1}^n s_i|$$ 观察题目中式子，不难想到如果对二进制拆位，那么相当于要求 ......

## **前言：** 输了，被水杯提醒我一直很失败。 ## 正片： ### 简要题意 > 求 $[l, r] \to p$ 的路径的交的边权和。 ### Solution：$O(n \log^2 n)$ 巨大分讨做法。 考虑分类讨论。 其一，$p$ 根本就不属于路径上的点，这个求区间 LCA 可以解 ......

怎么 ARC 还能撞题的？只能说 Kubic 牛逼。 首先显然没法保序回归。考虑用类似于凸壳优化 DP 的做法解决原问题（也就是 P4331）： - 设 $dp_{i,j}$ 表示考虑前 $i$ 位，$x_i=j$ 的最小代价，显然有 $dp_{i,j}=\min_{k\le j}\{dp_{i-1 ......

[题面传送门](https://www.luogu.com.cn/problem/P8923) 这不是保序回归板子吗（ 首先你拿保序回归通法做这个题那是一点前途没有，所以你考虑一点更优秀的方法。 众所周知保序回归 $L_{2k+1}$ 问题可以slope trick。考虑设 $f_{i,j}$ 表示 ......

首先发现一个性质：对于一组询问，如果答案不是 $-1$，那么必然存在最优正方形满足，要么三个边界上存在给定的点，要么两个边界 + 一个对角上存在给定的点，这是因为如果一个正方形只顶住了两个边界，那么如果这两个边界是邻边的话正方形肯定可以继续扩大，如果是对边的话我们可以将正方形水平方向上移动直到其卡住 ......

『MdOI R1』Treequery 前置知识：主席树，虚数，倍增，最近公共祖先 题目描述 给定一棵 $n$ 个点的无根树，边有边权。 令 $E(x,y)$ 表示树上 $x,y$ 之间的简单路径上的所有边的集合，特别地，当 $x=y$ 时，$E(x,y) = \varnothing$。 你需要 实时 ......

题目传送门 这一题其实很简单，只是要想到正确方法 ~~我一开始用了奇怪的搜索~~ ①无解的情况： 看上去很离奇，实际上略加思索就会发现，如果输入 $n$ 为偶数，那么就铁定无解。证明过程如下： 令 $n\bmod{2}=0$，人距离 $n$ 点的距离为 $dis$ ，则当走出第一步（步长为 $1$） ......