mip001's Blog

题意：给定长度为 $n$ 的序列 $a$，令 $f(l,r,x)$ 为 $a[l,r]$ 内 $x$ 的出现次数，$m$ 次询问，找到一个 $p$ 使得 $f(1,p,x)\times f(p+1,n,y)$ 最大，输出最大值。

$1\leq n,m\leq 10^5,1\leq a_i\leq 10^9$

纪念我本场唯一一道赛时过的题

题意：有一个长度为 $10^9$ 的序列 $a$，初始均为 $0$。给定 $n$ 个序列上的区间 $[l_i,r_i]$。进行 $m$ 次操作，每次给定 $p,x$，表示让 $a_p$ 加上 $x$。每次操作之后，令区间 $[l_i,r_i]$ 的权值为 $\sum\limits_{j=l_i}^{r_i} a_j$，你需要找到这 $n$ 区间中的最大权值。

$1\leq n,m\leq 4\times 10^5$

题目传送门

题目翻译：

给定长度为 $n$ 的序列 $a$。对于 $1\leq i<j\leq n$，若不存在 $k\in[1,n]$ 使得 $a_k\mid a_i$ 且 $a_k\mid a_j$ 那么 $(i,j)$ 是好的。求出好的数对数量。$a_i,n\leq 10^6$。

注意到若 $a_k\mid a_i$ 且 $a_k\mid a_j$，那么 $a_k$ 一定也能整除 $\gcd(a_i,a_j)$。那么我们可以通过枚举 $g$，找出最大公约数为 $g$ 的数对的个数 $f_g$，最后答案即为 $\sum f_g[\forall 1\leq k\leq n,a_k\nmid g]$。

传送门

简要题意：求长为 $n$ 的排列的波动序列的个数。

考虑 DP，设 $f_{i,j}$ 表示长度为 $i$ 的排列中，不合法元素有 $j$ 个的方案数，其中不合法元素指的是一个排列里既不是山峰也不是山谷的元素。显然我们最后要的答案即为 $f_{n,0}$。下面考虑转移

可以考虑如何从 $f_i$ 推 $f_{i+1}$。这其实相当于在长度为 $i$ 的排列中插入一个数 $i+1$，显然 $i+1$ 就是是这个排列里最大的数了。容易发现，插入这个数后这个排列的不合法元素要么不变，要么加一，要么减一，那么我们分别分析这三种情况。

我就是来水博客的

Day 1

T1 划

题意：给一个长度为 $n$ 的序列 $a$ 和一个 $d$，求最长的子区间 $[l,r]$，使得区间内的数排序之后相邻元素相差不超过 $d$，要求输出找到的区间长度。$n\leq 3\times 10^5,0\leq a_i\leq 10^9$

即找到最大的区间使得每个除了区间最大值以外的元素 $x$ 都有 $\leq x+d$ 的元素存在。

那么我们只需要跑出所有元素的左边和右边第一个 $\leq x+d$ 的元素，这个可以用 $set$ 维护；还需要知道所有元素的左边和右边最大的区间使得该元素为此区间的最大值，可以用单调栈维护

然后枚举 $r$ ，用线段树维护其最小的左端点即可，时间复杂度为 $O(n\log n)$。

基本概念

定义

记一个关于 $x$ 的式子：

$$f(x)=\sum\limits_{i=0}^na_i\times x^i$$

为一个 $n$ 次多项式。其中 $a_i$ 为常数，$n$ 为该多项式的度，也称次数，记作 $\deg f$。

显然，$f(x)$ 可以看作一个关于 $x$ 的 $n$ 次函数 $y=f(x)$。

这个 PPT 里面前半部分内容更完善

由于时间紧迫，本文不会太详细，并且由于 OI 不重视证明，本文很多时候可能只给出证明链接。

定理太多证明太难怎么办？证什么，背结论即可

2.1 记号

有确定界限的形式

我们要对一个有确定界限的式子求和：

$$a_1+a_2+\cdots+a_n$$

其中每个 $a_k$ 都是用某种方式定义的一个数。

我们可以用求和符号 $\sum$ 将其表示成这样：

$$\sum\limits_{k=1}^{n}a_k$$

我太弱了，现在才学莫队

以下均假设 $n,m$ 同阶。

普通莫队

简介

莫队算法主要用于解决离线区间查询等问题，若区间 $[l,r]$ 的答案能够 $O(1)$ 转移到与 $[l,r]$ 相邻的区间（即 $[l-1,r],[l+1,r],[l,r-1],[l,r+1]$），那么就可以使用莫队算法在 $O(n\sqrt{n})$ 内求出所有询问的答案。