跟 BZOJ 3224 不同的是优先级是题目中给定的，且不同所以把 sz 域删掉就好 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n, cnt, rt; int maxval, minval; struct node{ int lc, rc; int val, pri; int num; }tr[maxn]; int NewNode(int v, int num){ tr[++cnt].val = v; tr[cnt].pri ...

平衡树标准功能（1）插入（2）删除（3）查询数 x 的排名（4）查询排名为 x 的数（5）求 x 的前驱（6）求 x 的后继 题目为：zngg课程的第四讲第二题：普通平衡树 #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10; int n, cnt, rt; struct node{ int lc, rc; int val, pri; int num, sz; }tr[maxn]; int NewNode(int v){ tr[++cnt].val = ...

模板裸题矩阵快速幂借用了 zngg 的矩阵乘，写个快速幂就好了 #include <bits/stdc++.h> using namespace std; #define ll long long const int MAX_MAT = 20; const ll mod = 9973; int T, n, k; struct Mat{ ll a[MAX_MAT][MAX_MAT]; Mat(){ for(int i = 0; i < MAX_MAT; i++){ for(int j = 0; j < MAX_...

为什么是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] = dp[i-1][0]同理，左右侧之间是符号 那么，dp[i][0] = dp[i-1][0] + dp[i-1][1]dp[i][1] = dp[i-1][1]可见，第 i 层的状态可以由第 i-1 层的状态得到 为什么是矩阵？由 DP 可以得到矩阵。因为，上面的写法，就是矩阵乘法的形式 层数的...

各种图示，懒得找，请百度一下理解是，为什么会到 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的二进制表示以10结尾，那么i%2==0，i%4==2，那么c[i]=a[i-1]+a[i]，例如c[2]=a[1]+a[2], c[6]=a[5]+a[6]当k=2时，表示i的二进制表示以100结尾，那么i%4==0，i%8==4，那么c[i]=a[i-3]+a[i-2]+a[i-1]+a[i]=c[i-...

要求 [L,R] 区间的运算，怎么在 O(1) 的时间内，利用 [1,R] 与 [1, L-1] 的结果算出来A 思路：矩阵这是 N 个杯子，N 个球，建立一个 N * N 的矩阵，每进行一次操作，杯子交换也好，球移动也好，就是进行一次矩阵乘法运算。所以不管运算多少次，只要记得 [1, L-1] 和 [1,R] 的操作。乘 [1,R]， 除 [1, L-1]即可。当然，除在矩阵中，就是乘逆矩阵。矩阵代码会很麻烦。B 思路：群论把（0,1,2,3,4,5,6,7,8,9）想成一个圈无论怎么换，都是在这个圈中对元素进行交换。找到某种方法，对区间 [1, L-1] 的操作取消即可。 #include...

这个题从题面到解法都是很新颖的先跳出前缀和这个框架，想想这个题在干什么N = 20M = 1e5数据范围很多时候会提示数组怎么开，以及算法复杂度是多少Q1：这个复杂度，提醒什么？2表示这N个物品的某一个，取，还是不取Q2：20维度的数组开不下，咋办？开成一维的，用二进制位压缩之后才会想到前缀和：因为要维护子集合与超集合 把 N 个物品理解为向量，先想二维的情况F[A][B] = v[A][B]F[A][B] += F[0][B] + F[A][0]推广到 N 维：F[A][B][C][D][E]... = v[A][B][C][D][E]...F[A][B][C][D][E]... += v[...

这个题，zngg在讲课的时候案例举得非常明确和详细了，记录一下把题意转化一下：考虑前面的1，对于后面位置的 x 产生的影响如：1abcdefg1对于a的影响，是11对于b的影响，是21对于c的影响，是3依次类推这些影响，什么时候要累加到答案里呢？当abcdefg里某些位置的数是1的时候所以，这是考虑到单个1的贡献，在abcdefg，会对应于123456789 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0（1） 0 1 1 1 2 2 2 2 2 0 1 2 3 5 7 9 11 13在把数位上是1的贡献对应好加起来就好了最难的还是思维转换，从一个数学定义，如何联想转化...

前缀和差分不再过多介绍这个题思路是在一维数组上多做几阶差分然后就可以把原数组在 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的差分： 0 0 0 1 2 3 4 5 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 0 type 3的差分： 0 0 0 1 4 9 16 25 0 0 0 1 3 5 7 9 0 0 0 1 2 2 2 2 0 0 0 1 1 0 0 0这个题就友好在，所有的操作都是在[?,n] 的区...

学习链接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] = B[0] + B[1] + B[2] + ... + B[n]根据以上式子，可以推导得： B[0] = A[0] B[k] = A[k] - A[k - 1]定义：A 数组是 B 数组的前缀和，B 数组是 A 数组的差分由于这两个数组都是一维的，所以也可以叫做一维前缀和和一维差分 Q1：前缀和有什么...

前缀积要求Ai * A(i+1) * A(i+2) * ... * A(j)只需要知道前缀积 B(j) 和 B(i-1)，Ai * A(i+1) * A(i+2) * ... * A(j) = B(j) / B(i-1)在取模的意义下除法 = 乘法逆元 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e5 + 10; const ll MOD = 1e9 + 7; ll a[maxn], x; int N, M; int l, r; ll pow_mod...

int find(int x){ if (x != fa[x]) fa[x] = find(fa[x]); return fa[x]; } void tarjan(int u){ vis[u] = 1; for(int i = head[u]; i; i = e[i].nxt){ int v = e[i].v, w = e[i].c; if (!vis[v]){ dis[v] = dis[u] + w; tarjan(v); fa[v] = ...

void ST_create(){ k = log2(N); for(int j = 1; j <= k; j++) for(int i = 1; i <= n - (1<<j) + 1; i++) F[i][j] = F[F[i][j-1]][j-1]; } int LCA_ST_query(int x, int y){ if (d[x] > d[y]) swap(x, y); for(int i = k; i >= 0; i--) if (d[F[y][i]] &g...

POJ3264ST模板题，区间最大值 - 区间最小值 //#include <bits/stdc++.h> #include <algorithm> #include <stdio.h> #include <math.h> using namespace std; const int maxn = 50050; int Max[maxn][20], Min[maxn][20]; int H[maxn]; int N, Q; void ST_Create(){ for(int i = 1; i <= N; i++) ...