Codeforces Round #572 (Div. 2) 题解题意给出一个长度为 $n(\le 1000)$ 的序列和 $k$ ，求所有长度为 $k$ 的子序列中美丽值之和。美丽值定义为序列中的数两两之间差值的最小值。题解利用差分的思想。令 $g(x)$ 为美丽值 $\geq x$ 的子序列个数，那么答案就是 $\sum_{i=1}^\infty g(i)$ 。先把序列从小到大排序，这样...
题意有 $N$ 天，每天剩余教室为 $R_i$ 个。有 $M$ 个人要借教室，从 $S_i$ 借到 $T_i$ 。问能否满足所有人，如果不行则输出第一个不满足的人。$N,M\le 10^6$ 。题解本来还想写线段树查询最小值的，然后发现二分+差分就能解决。做法就是二分答案，然后差分修改后验证是否有 $<0$ 的。#include<bits/stdc++.h>
using ...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(x y)}$ 的询问，求 $\sum\limits_{i \le x} \text{dep}(\text{LCA}(i,y))^k$ 。其中点数 $N\le 50000$ ，询问数 $M\le 50000$ 。...
题意给出一棵树，定义 $\mathrm{dep}[i]$ 为 $i$ 的深度，$\mathrm{LCA}(i,j)$ 为 $i$ 与 $j$ 的最近公共祖先。有形如 $\text{(l r z)}$ 的询问，求 $\sum\limits_{l\leq i\leq r} \mathrm{dep}[\mathrm{LCA}(i,z)]$ 。其中点数 $N\le 50000$ ，询问数 $M\l...