CF 643G Choosing Ads（线段树）

2021-03-29
题解
约 785 字 预计阅读 2 分钟

题目链接

题目描述

给定一个长度为 $n$ 的序列和一个整数 $p$

有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p%$ 的数

输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}{p} \rfloor$

$n,m \le 1.5 \times 10^5$

$20 \le p \le 100$

阅读更多

Luogu P2824 [HEOI2016/TJOI2016]排序（线段树，二分答案）

2021-03-23
题解
约 833 字 预计阅读 2 分钟

题目链接

题目描述

给出一个 $1$ 到 $n$ 的排列，现在对这个排列序列进行 $m$ 次局部排序，排序分为两种：

  • 0 L R 表示将区间 $[L, R]$ 的数字升序排序
  • 1 L R 表示将区间 $[L, R]$ 的数字降序排序

注意，这里是对下标在区间 $[L, R]$ 内的数排序

最后询问第 $q$ 位置上的数字

$ n, m \leq 10^5$

阅读更多

二项式反演

2021-03-17
算法
约 175 字 预计阅读 1 分钟
主要形式 形式一 $$f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)$$ 形式二 $$f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)$$ 形式三 $$f(n)=\sum\limits_{i=n}^m(-1)^i\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i}\dbinom{i}{n}f(i)$$ 形式四 $$f(n)=\sum\limits_{i=n}^m\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i-n}\dbinom{i}{n}f(i)$$ 证明 反演基本形式如下 $$f(n) = \sum\limits_{i=0}^n{a_i}g(i)$$ $$g(n) = \sum\limits_{i=0}^n{b_i}f(i)$$ 在形式一中，有 $a_i = b_i = (-1)^i\dbinom{n}{i}$ 要证 $$f(n)=\sum\limits_{i=0}^na_ig(i)\Longrightarrow g(n)=\sum\limits_{i=0}^nb_if(i)$$ 只要证 $$g(n)=\sum\limits_{i=0}^nb_if(i)=\sum\limits_{i=0}^nb_i\sum\limits_{j=0}^ia_jg(j) = \sum\limits_{j=0}^ng(j)\sum\limits_{i=j}^nb_ia_j$$ 只要证 $$\sum\limits_{i=j}^nb_ia_j=[j=n]$$ 只要证 $$\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}=[j=n]$$
阅读更多

CF 1188C Array Beauty（DP）

2020-12-03
题解
约 387 字 预计阅读 1 分钟

题目链接

题目描述

给出一个序列 $a[1…n]$ 和 $k$

求 $a$ 所有长度为 $k$ 的子序列的价值和

定义一个序列 $b[1…k]$ 的价值为 $min(abs(b_i-b_j))$，即最接近的两个数的差

$1 \le k,n \le 10^4$

阅读更多