开开心心写

数据结构专题班

ACM - dp(1) ACM - 二分(8) ACM - 数学(1) ACM - 矩阵(1) ACM-线段树(1) ACM题解(245) Android(3) angr(3) Crypto(5) CTF之旅(84) Linux(8) pwn(1) python(6) reverse(3) ubuntu(1) Windows(4) 大作业(1) 恶意代码分析实战(43) 数学(4) 未归档(4)

/ 注册

全部文章 / 数据结构专题班（共15篇）

BZOJ - 3196 - 牛客竞赛数据结构专题班平衡树 - C题

树套树是指在一个树形数据结构上，每个节点都不再是一个节点，而是另一种数据结构。线段树可用于：点更新、区间更新、区间查询平衡树可用于：第 k 小、排名第 k 的数、前驱、后继将两者结合起来，就是线段树套平衡树用线段树维护区间，再用平衡树维护对区间中的动态修改。本题包括 5 种操作：区间排名、区间第...

2021-09-09

0 333

POJ - 3481 - 平衡树模板题2

跟 BZOJ 3224 不同的是优先级是题目中给定的，且不同所以把 sz 域删掉就好 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n, cnt, rt; int maxval,...

2021-09-08

0 407

BZOJ - 3224 - 平衡树标准模板题

平衡树标准功能（1）插入（2）删除（3）查询数 x 的排名（4）查询排名为 x 的数（5）求 x 的前驱（6）求 x 的后继题目为：zngg课程的第四讲第二题：普通平衡树 #include <bits/stdc++.h> using namespace std; const int ...

2021-09-07

0 429

专题班前缀和练习题 - E - 智乃酱的双塔问题

为什么是DP？设 dp[i][0] 是左边第 i 层的方案数dp[i][1] 是右边第 i 层的方案数如果，左右侧之间是符号 /那么，dp[i][1] = dp[i-1][0] + dp[i-1][1]，意思是，右边的第 i 层可以通过左边第 i-1 层和右边第 i-1 层上来dp[i][0] = ...

2021-08-23

0 524

树状数组原理与代码

各种图示，懒得找，请百度一下理解是，为什么会到 O(logn)c[i]对于a[i]的管理是按照二进制位的对于某个i，把它转为二进制设最后有k个连续的0当k=0时，表示i的二进制表示以1结尾，那么i就是奇数，那么c[i]=a[i]，例如c[1]=a[1], c[3]=a[3]当k=1时，表示i的二进制...

2021-08-22

0 536

专题班前缀和练习题 - F - 牛牛的猜球游戏

要求 [L,R] 区间的运算，怎么在 O(1) 的时间内，利用 [1,R] 与 [1, L-1] 的结果算出来A 思路：矩阵这是 N 个杯子，N 个球，建立一个 N * N 的矩阵，每进行一次操作，杯子交换也好，球移动也好，就是进行一次矩阵乘法运算。所以不管运算多少次，只要记得 [1, L-1] 和...

2021-08-19

0 365

专题班前缀和练习题 - B - 智乃酱的子集与超集

这个题从题面到解法都是很新颖的先跳出前缀和这个框架，想想这个题在干什么N = 20M = 1e5数据范围很多时候会提示数组怎么开，以及算法复杂度是多少Q1：这个复杂度，提醒什么？2表示这N个物品的某一个，取，还是不取Q2：20维度的数组开不下，咋办？开成一维的，用二进制位压缩之后才会想到前缀和：因为...

2021-08-19

0 599

专题班前缀和练习题 - G - 牛牛的Link Power I

这个题，zngg在讲课的时候案例举得非常明确和详细了，记录一下把题意转化一下：考虑前面的1，对于后面位置的 x 产生的影响如：1abcdefg1对于a的影响，是11对于b的影响，是21对于c的影响，是3依次类推这些影响，什么时候要累加到答案里呢？当abcdefg里某些位置的数是1的时候所以，这是考虑...

2021-08-16

0 446

专题班前缀和练习题 - H - 小w的糖果

前缀和差分不再过多介绍这个题思路是在一维数组上多做几阶差分然后就可以把原数组在 O(n) 的维护，转化成为在差分数组上 O(1) 的维护做了几阶差分，在求前缀和的时候，就求几次，就 ok 了 type 1的差分： 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 type 2的差分：...

2021-08-16

0 571

前缀和与差分总结 - HDOJ 1556

学习链接1学习链接2学习链接3学习链接4学习链接5 再来说说自己的理解先来写几个式子，再做定义 A[0] = B[0] A[1] = B[0] + B[1] A[2] = B[0] + B[1] + B[2] A[3] = B[0] + B[1] + B[2] + B[3] ... A[n] = ...

2021-08-15

0 474