2019暑期集训第十二讲：高级数据结构（三）
分块分块是一种思想，对于一些题目，首先线段树等数据结构，分块作为一个备用方案
它擅长做的一些事情
区间和
将序列分段，每段长度$T$，那么一共右$n\over T$段，大段维护小段暴力，复杂度$O({n\over T}+T)$
也可以维护很多种前缀和进而做到$O(1)$查询
对询问分块
如果操作次数比较少，可以先把操作记下来，在询问的时候加上这些操作的影响
T个操作，则修改$O(1)$，询问$O(T)$
莫队莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
形式假设 n=m，那么对于序列上的区间询问问题，如果从$[l,r]$的答案能够$O(1)$扩展到 $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$（即与 $[l,r]$ 相邻的区间）的答案，那么可以在$O(n\sqrt n)$ 的复杂度内求出所有询问的答案。
实现
排序：对于区间$[l,r]$，以$l$所在块的编号为第一关键字，以$r$为第二关键字从小到大排序
实现：先排序，顺序处理每一个询问，暴力从上一个区间的答 ...
2019暑期集训第八讲：数据结构进阶（一）
数据结构进阶(一)主讲人：孙翔
线段树为什么要线段树？题目一： 10000个正整数，编号1到10000，用A[1],A[2],A[10000]表示。 修改：无 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.
方法一：对于统计L,R ，需要求下标从L到R的所有数的和，从L到R的所有下标记做[L..R],问题就是对A[L..R]进行求和。这样求和，对于每个询问，需要将(R-L+1)个数相加。
方法二：更快的方法是求前缀和,令 S[0]=0, S[k]=A[1..k] ，那么，A[L..R]的和就等于S[R]-S[L-1]，这样，对于每个询问，就只需要做一次减法，大大提高效率。
题目二： 10000个正整数，编号从1到10000，用A[1],A[2],A[10000]表示。 修改：1.将第L个数增加C （1 <= L <= 10000） 统计：1.编号从L到R的所有数之和为多少？ 其中1<= L <= R <= 10000.
再使用方法二的话，假如A[L]+=C之后，S[L],S[L+1],,S ...
2019暑期集训第七讲：动态规划(II)
DP状压DP 首先回顾一下位运算
与 &
或 |
异或 ^
取反 ~
左移 <<
右移 >>
^ 运算的逆运算是它本身
取反是对 1 个数 $num$ 进行的计算，~ 把$num$种的0 和 1 全部取反补码——正数的补码是其（二进制) 本身，负数的补码是其（二进制）取反后加一
右移在C++中将直接舍弃右侧多余位，左侧则较为复杂，无符号数会在左侧补0，对于有符号书，则会用最高位的数补齐[注]：
1. 左移和右移是有返回值的，并非对$num$本身进行操作
2. 左移和右移优先级低于四则运算，`x<<1+1` 会被解释为`x<<(1+1)`，所以一般最好都加上括号
一些应用
num<<i 相当于$num\times 2^i$ ，而num>>i 相当于$num \div 2^i$ 。效率要比 % 和 / 操作快得多（60%？）
当$num>0$时两者并没有差别，但是当$num<0$时，普通除法时向0取整，而右移是向下取整
num * 10 = (num << 1) + (nu ...
2019暑期集训第六讲：动态规划(I)
动态规划（线性，区间，树形）对于动态规划 我们所需要确定的肯定就是以下几种元素
状态（阶段）
我们确定的状态要保证当前的状态不会对于后面的状态产生影响 这个条件也被叫做无后效性 并且这个状态能够表示出所有的状态
2.决策
我们利用什么样的决策从前面一个阶段转移到我当前的阶段过来（可能是前面的阶段去最小值，最大值之类的）
开始写代码的时候要确定状态的起始条件（也就是边界条件） 再确定状态的最总目标 （也就是我们要求的答案）
1.线性dp具有线性“阶段”划分的动态规划算法被称为线性dp
题目 1：
给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为1 * 1或更大的连续子阵列。矩形的总和是该矩形中所有元素的总和。在这个问题中，具有最大和的子矩形被称为最大子矩形。例如，下列数组：
0 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2其最大子矩形为：
9 2-4 1-1 8它拥有最大和15
对于这个问题 我们当然可以直接暴力枚举这个区间的起始端点和结束端点来求答案，但是这个方案的复杂度太高了，我们可以想到之前做过的最大的连续子序列和的线性dp来解 ...
2019暑期集训第五讲：基础数据结构
数据结构基础栈1.定义 栈（Stack）又称堆栈，它是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把此端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底。向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是把栈顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。
2.栗子 放盘子，装东西….
3.实现 实现一般有两种：第一种用一个数组和一个变量（栈顶指针）来实现。第二种用STL自带的stack。
常规操作：
1234567891011121314151617#include<iostream>#include<stack>using namespace std;stack<int> s;int main(){ s.push(10);//入栈 cout<<s.size()<<endl;//栈大小 int t=s.top();//栈顶元素 cout<<t ...
2019暑期集训第四讲：字符串基础
字符串基础1.字符串匹配1.暴力算法123456for (i = 0; i < n - m + 1; i++) { for (j = 0; j < m; j++) { if (a[i + j] != b[j]) break; } if (j == m) ans.push_back(i); }
2.哈希将string映射为int 每一个字符串代表一个数字 时间复杂度变为O(n+m)
转化方法可以采用
f(s) = \sum{s[i]*b^i}(modM)12345678ll hashs(char s[])//上述公式相当于把一个字符串看成一个b进制数{ int len=strlen(s); ll ans=0; for (int i=0;i<len;i++) ans=(ans*base+(ll)s[i])%mod; return ans;}
b与M应当是互质的（不然取余的时候直接约了）
在输入随机的情况下，这个求出 ...
2019暑期集训第二讲：组合数学&概率&数学期望
主讲人：韩耀东
时间：7.19
组合数学 & 概率期望DP组合数学1. 排列组合1. 加法原理 完成一列事的方法有 n 类，其中第 i 类方法包括$a_i$种不同的方法，且这些方法互不重合，则完成这件事共有 $a_1 + a_2 + \cdots + a_n$ 种不同的方法
2. 乘法原理 若完成一件事需要 n 个步骤，其中第 i 个步骤有 $a_i$ 种不同的完成方法，且这些步骤互不干扰，则完成这件事共有 $a+1 a_2 \cdots * a_n$ 种不同的方法
两原理的区别：
一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”
3. 排列数在 $n$ 个不同元素种，任取 $与均为自然数，下同m(m\leq n,m与n均为自然数，下同)$ 个元素按照一定的顺序排成一列，叫做从$n$个不同元素中取出$m$ 个元素的一个排列；产生排列的个数叫做从 $n$ 个不同元素中取出 $m$个元素的排列数，用符号 $A_n^m$ 来表示
A_n^m = n(n-1)(n-2) \cdots (n-m+1) = ...