标签:算法-差分

题意有 $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$ 。...
题解 数据结构-树链剖分 算法-差分
NOI/NOI+/CTSC
题意给出一棵树,定义 $\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...
题解 数据结构-树链剖分 算法-差分
NOI/NOI+/CTSC