传说中的ZKW线段树 比一般线段树快
这个是ZKW讲课的课件
线段树是二叉搜索树的一种。与一般的二叉搜索树不同的是，线段树保存的是所有元素可能取的值，而不是每个元素。通常情况下，线段树只用叶节点表示每个值。而其余的节点对应的就是一个范围。
2021-07-14 11:45:30
474KB
1
Alice和Bob又在挑战智力，这次的模式是这样的，Alice写下若干个数给Bob，之后会发出若干指令，让Bob给某数加上一个数（A），或者给某数减去一个数（S），或者查询某两个数之间所有数字之和（Q），有时他们也身份互换，反应速度最快的人将得到“速算小能手“奖章。你有好办法么？
输入：第一行为数的个数N，第二行是这N个数，从第三行开始表示每个操作，第一个字母代表操作的种类，A和S后面的两个数i,j分别表示给第i个数加上或减去j，Q i,j表示查询i和j之间数字之和。
输出：若干行，每行为一次查询的结果。
样例输入：
10
1 2 3 4 5 6 7 8 9 10
Q 1 3
A 3 6
Q 2 7
S 10 2
A 6 3
Q 3 10
样例输出：
6
33
59
2021-05-27 09:47:39
2KB
1
T1
本题极其无聊，3T强行捏成1T，差最大 显然是 前一半后一半，差最小显然是间隔着放，方案数显然是卡特兰数列
关于卡特兰数列，直接放公式了h(n)=C(2n,n)/(n+1) (n=0,1,2,...) or h(n)=c(2n,n)-c(2n,n-1)(n=0,1,2,...)
也就是2n 个数0 1，保证在任何位置都有：之前的1的个数<= 0的个数 之类的问题
维护：
1.求和数组，每次右半边的和 - 左半边的和
2.奇正偶负数组，每次询问时判断L是奇是偶在考虑正负
3.组合数
2021-03-18 11:09:12
4KB
1