本文参考 Codeforces edu线段树教程 ac-library lazy segtree 本文的代码实现基于递归式线段树，下标从 $1$ 开始，维护的区间是 $[l,r]$（左闭右闭）；但是引用的codeforces教程默认区间是 $[l,r)$（左闭右开）。 区间修改+单点查询 区间加+单点查询 给定一个 n 个元素的数组 a，处理以下两…

AtCoder Beginner Contest 371题解 E - I Hate Sigma Problems 定义函数 $f(l,r)$ 表示 $A[l],A[l+1],\cdots,A[r]$ 中不同的元素个数，求$$\sum_{i=1}^N\sum_{j=i}^N f(i,j).$$ 其实就是求数组 $A$ 中所有区间的元素种类数。可以通过…

本文假设需要排序的数组是 $A[]$，并且是不降序的排列 $(A[j]\ge A[i])_{j\gt i}$。 默认数组下标从 $0$ 开始。 插入排序 基础插入排序 一句话概括：从左往右遍历数组，将每次遍历到的元素 $A[i]$ 向左移动到可能的最左侧的位置 $j$，要求满足 $A[j+1]\gt A[j]$ 。（有点不严谨，但不影响理解） vo…