zcmimi's blog
avatar
zcmimi
2020-03-25 17:13:00

整体二分是离线算法

顾名思义就是将所有答案一起二分

solve(l,r,st,ed)表示答案在[l,r],解决第sted个询问或操作

以静态区间第k小为例,[LG P3834 【模板】可持久化线段树 1(主席树)](https://www.luogu.com.cn/pro

avatar
zcmimi
2020-03-20 21:28:00

使用fread加速

仅数字:

```cpp namespace IN{const int str=1<<20;static char in_buf[str],in_s,in_t;bool __=0;inline char gc(){return (in_s==in_t)&&(in_t=

avatar
zcmimi
2020-03-20 20:36:00

二维偏序

先按 第一维 排序, 第二维 用数据结构维护

例题: [SHOI2007]园丁的烦恼

离线操作

先将每个询问拆成4个点查询

(1,1)(x,y)中点数为s(x,y).

avatar
zcmimi
2020-03-15 17:10:00

前置知识: 狄利克雷卷积

求积性函数f的前缀和:

S(n)=\sum_{i=1}^nf(i)

大部分题目都是可以线性筛的,可是某些丧心病狂的出题人会: n\le 10^{12}!

这时候需要用杜教筛了

我们构造另

avatar
zcmimi
2020-03-14 22:46:00

数论函数

  1. 加法

    逐项相加

    (f+g)(x)=f(x)+g(x)

  2. 数乘

    (xf)(n)=x\cdot f(n)

定义

两个数论函数的狄利克雷卷积∗

t=f*g等价于

$$t(n)=\sum_{i|n}f(i)

avatar
zcmimi
2020-03-12 20:40:00

该好好复习(总结)一下莫比乌斯函数了呢\mathcal{>_\omega<}

定义

$$ \mu (i)= \begin{cases} 1,i=1 \ (-1)^k,i=p_1\times p_2\times \dots \times p_k \ 0,rest \end{cases

avatar
zcmimi
2020-03-07 15:50:00

扩展中国剩余定理

给定方程组:

$$ \begin{cases} x \equiv a_1\ ({\rm mod}\ m_1) \ x\equiv a_2\ ({\rm mod}\ m_2) \ ... \ x \equiv a_n\ ({\rm mod}\ m_n) \end{cas

avatar
zcmimi
2020-03-06 10:17:00

一级标题

二级标题

三级标题

四级标题

链接

加粗

斜体

删除线

下划线

引用

表格:

表头 表头
单元格 单元格
单元格 单元格

|左对齐----|--居中对齐-

avatar
zcmimi
2020-03-02

Lucas定理

C_n^m\pmod p\equiv C_{n\mod p}^{m\mod p} \cdot C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\pmod p

就是一个组合数可以拆成P进制下的乘积

这个算法可以处理当m,n非常大

总结一下各种启发式合并

什么是启发式合并

可以算是一种技巧

比如要合并集合A,B,设|A|<|B|

这时候将 向B中插入A 的效率要比 向A插入B

这就是启发式合并的思想

Q: 很简单,但有什么用?

A: 假设我们要合并n个元素

5/74
Search
search