\(\mathcal{Part}\) 1. 前提提要
注意：本文为提高组难度的算法思想，主要为前缀和，差分等优化
因为是思想，讲的会比较玄乎，能理解就好
\(\mathcal{Part}\) 2. 双指针
双指针通常解决区间问题
步骤是，确定一个右节点或左节点作为一个参考点，通常取右节点，记为 \(j\)
我们考虑一个刚好符合题目条件的最小节点，记为 \(l\)
双指针有个前提：当右指针往右移动时，左指针不可能往前走
解决步骤：
右指针往右跳，让左指针也往右跳，跳到符合条件为止，这就是题目要求的以 \(r\) 为右端点最长的区间
因为左指针和右指针都只会跳 \(n\) 次，总时间复杂度为 \(\mathcal{O}(n)\)
\(\mathcal{Practice}\) 1.
\(\mathcal{Practice}\) 2.
\(\mathcal{Part}\) 3. 前缀和
一维前缀和
我们有一个序列 \(A\)，我们要进行一下操作
- \(\mathcal{O}(n)\) 地预处理
- 给定一个 \(l\) 和 \(r\)，求 \(\sum_{l\le i\le r} A_i\)，时间复杂度为 \(\mathcal{O}(1)\)
我们记一个数组 \(B\) 满足
\[B_i=\sum_{1\le j\le i} A_j \]预处理 \(B\) 数组，时间复杂度为 \(\mathcal{O}(n)\)
我们要查询 \([l,r]\) 的值，也就是 \(\sum_{l\le i\le r} A_i\)，经过简单数学推导，如下
\[\begin{aligned} \sum_{l\le i\le r}A_i&=\sum_{1\le j\le r}A_j - \sum_{1\le k <l}A_k\\ &=B_r-B_{l-1} \end{aligned} \]通俗点来说，就是 \([l,r]\) 的值等于 \(B_r-B_{l-1}\)
前缀和在众多领域起着重大作用，以代码量小和快著称
弊端是：不能动态修改
二维前缀和
给定一个二维序列，记为 \(A\)，现要支持
- 给定两点 \((l_1,r_1)\) 和 \((l_2,r_2)\)，求以两点为矩形端点的矩形，里面所有数之和
记一个二维数组 \(B_{i,j}\) 为 \((1,1)\) 到 \((i,j)\) 的数之和
初始化 \(B_{i,j}=B_{i-1,j}+B_{i,j-1}-B_{i-1,j-1}+A_{ij}\)
证明平凡，自己画图
则两点 \((l_1,r_1)\) 和 \((l_2,r_2)\)，求以两点为矩形端点的矩形，里面所有数之和就为：
\[B_{l2,r2}-B_{l1-1,r2}-B_{l2,r1-1}+B_{l1-1,r2-1} \]推导过程平凡，请自己画图证明
多维前缀和
类比容斥原理
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 4. 差分
一维差分
现有一个序列 \(A\)，先要支持
- 动态修改 \([l,r]\) 的值
- \(O(n)\) 打印 \(A\) 序列的每个数
记一个数组 \(B\) 满足
\[B_i=A_i-A_{i-1} \]我们看看 \(A_i\) 等与什么
\[\sum_{1\le j \le i}B_j=\sum_{1\le j\le i}A_j-A_{j-1}=A_i \]也就是说，差分的前缀和等于原数组，简单的想，前缀和的差分等于差分
这三者就有机的连在一起了
接下来看怎么修改，记修改的数为 \(k\)
- 当 \(i=l\) 时，\(B_i'=(A_i+k)-A_{i-1}=B_i+k\)
- 当 \(i = r+1\) 时， \(B_i'=(A_{r+1}-(A_{r}+k))=B_i-k\)
- 当 \(i\in (l,r]\) 时，\(B_i'=(A_i+k)-(A_{i-1}+k)=B_i\)
通俗点说，就是修改 \([l,r]\) 的值时，只需要修改 \(B_l\) 和 \(B_{r+1}\) 的值即可
时间复杂度为：\(\mathcal{O}(1)\)
二维差分
类比 \(S_{i,j}=S_{i-1,j}+S_{i,j-1}-S_{i-1,j-1}+A_{ij}\)
因为 \(B\) 的前缀和为 \(A\)，则用 \(A\) 替代 \(S\)，\(B\) 替代 \(A\) 则
\[A_{i,j}=A_{i-1,j}+A_{i,j-1}-A_{i-1,j-1}+B_{i,j}\\ B_{ij}=A_{i,j}-A_{i-1,j}-A_{i,j-1}+A_{i-1,j-1} \]这就是二维差分的初始化了
我们考虑修改 \((u,v)\) 到 \((n,n)\) 的差分
- 当 \((i,j) = (u,v)\) 时，\(B'_{i,j}=(A_{i,j}+w)-A_{i-1,j}-A_{i,j-1}+A_{i-1,j-1}=B_{i,j}+w\)
可以证明，其他位置的差分值不变
可以推导 \((u,v)\) 到 \((x,y)\) 的差分值为
\[B_{u,v}+w,B_{u,y+1}-w,B_{x+1,v}-w,B_{x+1,y+1}+w \]证明平凡，类似后缀和
多维差分
和二维差分的推导过程一样
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 5.离散化
我们要将一个值域为 \((-\infty,\infty)\) 的数映射到 \((0,n]\) 之中
怎么做到呢？
我们知道，映射有个性质
- 每个数的大小关系不变
想到什么？排名是不是可以完美做到这一点？
所以，我们第一步是将原数组去重排序+排序
排序用 sort 人尽皆知，去重用什么呢？
使用 unique 函数，使用格式： unique(a.begin(),a.end())这里 a.begin(),a.end() 分别指数组的头指针和尾指针，普通数组用 a+1,a+1+n
- 注意一点：该函数的返回值是不属于去重数组的第一个地址，比如有个数组长度为 \(n\) ，去重数组长度为 \(k\) ，他的返回值就是 \(a_{k+1}\)的地址。
根据上面几点，我们可以推出公式。
k=unique(a+1,a+1+n)-(a+1)
这样我们就可以求出去重数组的长度了。
第二步，我们求排名
设这个数为 \(A_i\)，\(B\) 数组的排名为 \(k\)，则他在 \(A\) 数组的排名为 \(k\)
那怎么找 \(i\) 呢？这里使用一个函数：
lower_bound(a+1,a+1+n,x) 他返回的是第一个大于等于 \(x\) 的元素的地址，注意：必须有序。
于是，我们可以推出公式：
rk[i] = lower_bound(b + 1, b + 1 + k, a[i]) - b;
到此结束
因为 \(rk_i\) 存的是第 \(a_i\) 在 \(b\) 数组的下标，则
\[B_{rk_i}=A_i \]sort(b + 1, b + 1 + n);
int *ed = unique(b + 1, b + 1 + n);
for (int i = 1; i <= n; i++) {
rk[i] = lower_bound(b + 1, ed, a[i]) - (b + 1) + 1;
cout << rk[i] << ' ';
}
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 6. 位运算
基本位运算
- 按位与：\(x\&y\)，把两数的对应位做逻辑与
- 按位或：\(x|y\)，把两位的对应位做逻辑或
- 按位异或：\(x\oplus y\)，把两位对应位做逻辑异或
- 按位取反：\(!x\)，把 \(x\) 的每一位取逻辑非
- 左移：\(x<<y\)，把 \(x\) 的整体向左移动 \(y\) 位，高位抹去，低位补0，（\(x<<y=x*2^{y-1}\)）
- 右移：\(x>>y\)，把 \(x\) 的整体向右移动 \(y\) 位，低位抹去，高位补0，（\(x>>y=\cfrac{x}{2^{y-1}}\)）（向下取整）
单点修改：
- 将第 \(i\) 位修改为 \(1\)：
x |= 1<<(i-1) - 保证第 \(i\) 位为 \(1\)，修改为 \(0\)：
x^=1<<(i-1)
注意：\(<<\) 或 \(>>\) 的优先级比 \(-\) 低，则：\(1<<(i-1)=1<<i-1\)
求两个集合的交集，并集和对称差
可以把两个集合看成一个二进制数，则
\(x_i=0\) 表示 \(i\) 不在集合中，反之同理
两个二进制的与，或，异或可以达到需要效果
神器！\(bitset\)
用二进制表示集合时，普通的变量存不下这么大的二进制，我们可以使用 \(bitset\) 创建一个超长二进制
支持：所有位运算操作也支持修改这个串的某一位
时间复杂度为：\(\mathcal{O}(\cfrac{n}{w})\)，\(w\) 通常取 \(64\)
基本用法：
bitset<N> s表示创建一个二进制数s.set(i,0/1)表示在第 \(i\) 位设置成 \(0/1\)s.test(i)返回第 \(i\) 位的值s.count()返回 1 的数量s.reset()把 \(s\) 清空成 0s.flip()对二进制取反- 可以直接进行逻辑运算
注意：声明 \(bitset\) 时，\(N\) 必须是常量（CE不关我事（doge.
\(\mathcal{Practice}\)
见题单
\(\mathcal{Part}\) 7. 单调数据结构
单调栈
单调栈维护的是一个栈，里面的元素单调递增或单调递减
用于找后缀最大值。
定义：当 \(i\) 为后缀最大值时，当且仅当：对于所有的 \(i<j\le|A|\)，都有 \(A_i>A_j\)
因为栈内数据单调递减，所以对于一个在栈内的元素 \(A_i\)，他后面没有比他大的数（不然就被弹出了
所以留在栈内的都是后缀最大值
时间复杂度为：\(\mathcal{O}(n)\)
单调队列
单调队列维护的是一个队列，只不过里面的数的下标都严格在一个区间里
比你小的人都打不过，你应该出队
被单调队列了
$ Practice$
题比较难，所以我写了几篇题解，自己去看
\(\mathcal{P}art\) 8.倍增
倍增基本概念
我们先来考虑一个引论
- 任何一个 \(x\in \mathbb{N^*}\)，都可以拆成若干个 \(2\) 的正整数次幂之和
证明平凡
所以对于每一段区间，我们都可以拆成 \(\log n\) 个区间
倍增快速幂
我们要求 \(x^y \mod p\) 的值
\(x,y\le10^9\)
怎么办呢？
我们考虑使用倍增的思路：
\[x^y=(x^2)^{\frac{y}{2}} \]这里需要进行奇偶性判断，如果是奇数，则直接乘进答案中即可
时间复杂度为：\(\mathcal{O}(\log x)\)
\(\mathcal{Code}\)
typedef long long ll;
ll qpow(ll d, ll b, ll Mod) {
ll ans = 1;
while (b) {
if (b & 1) ans = ans * d % Mod;
d >>= 1; b = b * b % Mod;
}
return ans;
}
\(\mathcal{P}ractice\)
见题单
ST表
ST表是什么呢？他是专门解决 RMQ 问题的一个简便写法（比线段树好写多了
RNQ 问题
\(\mathcal{O}(n\log n)\) 的预处理，要求支持：
- 给定 \(l,r\) 要求 \(\max_{l\le i\le r}\{a_i\}\) ，\(\mathcal{O}(1)\) 的时间复杂度
根据我们倍增的知识，我们可以定一个 st 表，如下
记：\(f_{i,j}\) 表示 \([i,i+2^j-1]\) 这段区间的最大值，用人话来讲就是从第 \(i\) 为开始，连续 \(2^j\) 个数
状态转移方程也很好推：
\[f_{i,j}=\max \{f_{i,j-1},f_{i+2^{j-1},j-1}\} \]怎么记呢？爸爸的爸爸叫爷爷！
是不是很好记(doge.
时间复杂度为 \(\mathcal{O}(n\log n)\)
那怎么查询呢？
可以用我们上面证的，一段区间可以拆成若干个2的正整数次幂长度的区间，对这个区间进行二进制分解即可
但这样的时间复杂度为 \(\mathcal{O}(\log n)\)
因为是最大值，所以比较区间可以重叠！
这一段区间可以跳 \(\log n\) 次，所以我们就左端点跳 \(\log n\) 次，右端点跳 \(\log n\) 次，这样虽有重叠，也无伤大雅
时间复杂度为 \(\mathcal{O}(1)\)
\(\mathcal{C}ode\)
n = read(), m = read();
for (int i = 1; i <= n; i++) f[0][i] = read();
for (int t = 1; (1 << t) <= n; t++)
for (int i = 1; i + (1 << t) - 1 <= n; i++)
f[t][i] = max(f[t - 1][i], f[t - 1][i + (1 << t - 1)]);//注意优先级的问题
for (int l, r; m; m --) {
l = read(), r = read();
int len = r - l + 1, t = log2(len);
cout << max(f[t][l], f[t][r - (1 << t) + 1]) << "\n";
}
\(\mathcal{P}ractice\)
见题单
\(\mathcal{Part}\) 10.分治
简述分治算法
简单来说，就是原问题分成两个差不多一样的问题，先解决他们，在返回来解决自己
重要的是：你在做这一层的时候，你不要管下去后他怎么了，不然会晕的，把他默认成已知就行
基本步骤
- "分"：如何把大问题划分为更小的答案
- "合"：如何把小问题合并成更大的答案
归并排序
- “分“
很显然，当前区间的子任务就是长度一半的区间，即分成两个区间长度都为当前区分的一半
- "合"
重要部分是 “合”，即现在有两个有序的序列，要把他们合并到一个大的序列里，怎么做呢？
有序表合并，可以用我们刚讲过的双指针思想
即记 \(i\) 为 \(A\) 序列的起点，\(j\) 为序列 \(B\) 的起点
现在比较 \(A_i\) 和 \(B_j\)
- \(A_i>B_j\)，就将 \(B_j\) 加到答案序列里，同时 \(j\) 自增
- \(A_i<B_j\)，就将 \(A_i\) 加到答案序列里，同时 \(i\) 自增
最后如果 \(i\) 或者 \(j\) 没有跑完，就把后面的数直接加进去即可
注意到，答案序列只在原来区间的位置，所以起点和终点就是 \(l,r\)
\(\mathcal{C}ode\)
void solve (int l, int r) {
if (l == r) return ;
int mid = l + r >> 1;
solve(l, mid); solve(mid + 1, r);//分
int i = l, j = mid + 1, pos = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) b[pos++] = a[i++];
else b[pos++] = a[j++];
}
while (i <= mid) b[pos++] = a[i++];
while (j <= r) b[pos++] = a[j++];
for (int i = l; i <= r; i++) a[i] = b[i];
}
归并排序解决逆序对问题
逆序对问题：
现求 \(A\) 序列中满足 \((i,j)\)，\(i<j\) 且 \(A_i>A_j\) 的 \((i,j)\) 的数量
对于 \([l,r]\) 的区间，我们分治的去考虑问题，逆序对只有可能出在三种情况
- 全部出现在左区间
- 全部出现在右区间
- 横跨在两个区间之间
前两个操作可以在递归中完成
我们主要看第三个部分
令 \(i\) 为 \(A\) 序列的指针， \(j\) 为 \(B\) 序列的指针
还是分类讨论
- \(A_i>B_j\)，说明 \(A_{i…n}\) 的数都比 \(B_j\) 大，把后面的答案统计一下就行，再将 \(B_j\) 加到答案序列里，同时 \(j\) 自增
- \(A_i<B_j\)，就将 \(A_i\) 加到答案序列里，同时 \(i\) 自增
最后如果 \(i\) 或者 \(j\) 没有跑完，就把后面的数直接加进去即可
\(\mathcal{C}ode\)
void solve (int l, int r) {
if (l == r) return ;
int mid = l + r >> 1;
solve(l, mid); solve(mid + 1, r);
int i = l, j = mid + 1, pos = l;
while (i <= mid && j <= r) {
if (a[i] <= a[j]) b[pos++] = a[i++];
else b[pos++] = a[j++], ans += mid - i + 1;//改动
}
while (i <= mid) b[pos++] = a[i++];
while (j <= r) b[pos++] = a[j++];
for (int i = l; i <= r; i++) a[i] = b[i];
}
CDQ分治
这东西，有亿点恶心，耗了我两年半进行理解……
一维偏序
排序即可
二维偏序
例子：逆序对
他就是用归并排序解决的一个二维偏序问题
例子：树状数组
现有一个序列，要支持两种操作
- 给定 \(x,k\) 要求 \(A_x\) 加上 \(k\) （单点修改
- 给定 \(x,y\)，要求 \(\sum_{x\le i\le y} A_i\)（区间查询
分析：
如果你要用数据结构，我也拦不到你
我们考虑二维偏序
记一个多元祖 \((t,x,w,op)\)，\(t\) 为操作编号，\(x\) 为操作位置，\(w\) 为修改值，\(op\) 为对答案的贡献倍数（1/-1)
对于一个查询操作 \(i\)，其结果就是所有满足 \(t_j<t_i\) 且 \(p_j<p_i\) 的查询 \(w\) 之和，类似顺序对问题
因为前面的数天生满足 \(t_j<t_i\)，我们只需要找到 \(p_j<p_i\) 的 \(w_j\) 之和
考虑分治
设 \(solve(l,r)\) 表示 \([l,r]\) 操作的贡献，\(solve(l,mid)\) 和 \(solve(mid+1,r)\) 时已知，因为左区间和右区间都已经满足两个条件
所以双指针即可
这里给上代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6 + 7;
struct Node{
int type, x, v, id;
bool operator < (const Node other) const {
return x == other.x ? type < other.type : x < other.x;//注意，先修改后查询
}//现区间没影响，合起来之后有影响
}A[MAXN], B[MAXN];
int n, m, cnt, Ans[MAXN], arr;
void CDQ(int l, int r) {
if (l == r) return ;
int mid = l + r >>1;
CDQ(l, mid), CDQ(mid + 1, r);
int i = l, j = mid + 1, sum = 0, tot = l;
while (i <= mid && j <= r) {
if (A[i] < A[j]) {
if (A[i].type == 1) sum += A[i].v;//双指针：让左节点一直跳，跳到不符合条件即可
B[tot ++] = A[i ++];
} else {
if (A[j].type == 2) Ans[A[j].id] -= sum;//跳完之后减上贡献
else if (A[j].type == 3) Ans[A[j].id] += sum;//或加
B[tot ++] = A[j ++];
}//记得是累加哦
}
while (i <= mid) B[tot ++] = A[i ++];
while (j <= r) {
if (A[j].type == 2) Ans[A[j].id] -= sum;//累加即可
if (A[j].type == 3) Ans[A[j].id] += sum;
B[tot ++] = A[j ++];
}
for (int i = l; i <= r; i ++) A[i] = B[i];
}
int main () {
cin >> n >> m;
for (int i = 1, x; i <= n; i ++) cin >> x, A[++ cnt].type = 1, A[cnt].x = i, A[cnt].v = x;
for (int i = 1; i <= m; i ++) {
int op, x, k;
cin >> op >> x >> k;
if (op == 1) {
A[++ cnt].type = 1, A[cnt].x = x, A[cnt].v = k;
} else {
A[++ cnt].type = 2, A[cnt].x = x - 1, A[cnt].id = ++ arr;//arr需相等
A[++ cnt].type = 3, A[cnt].x = k, A[cnt].id = arr;
}
}
CDQ(1, cnt);
for (int i = 1; i <= arr; i ++) cout << Ans[i] << '\n';
return 0;
}
三维偏序
题目：
这是一道三维偏序模板题，可以使用 bitset，CDQ 分治，KD-Tree 等方式解决。
有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 \(j\) 的数量。
对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。
$ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $。
解决：
第一步，先按第一关键字排序（sort）
第二步：用cdq对第二关键字排序
第三步：用树状数组维护第三关键字（类似用树状数组维护逆序对）
具体的和一些细节：
我们先用 sort 对第一关键字进行排序，保证每个符合条件的 \(j\) 都在 \(i\) 的右边
我们直接上cdq对第二关键字排序
最后用树状数组就行
如果有重复的情况怎么办？
考虑到有可能有 \(j\) 在 \(i\) 的右边，导致没算全，但是最右边的 \(i\) 是绝对正确的，所以我们可以把序列排序，然后把连着的相同的全部赋值成最后一个数即可
注意细节
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
const int MAXM = 2e5 + 7;
struct Node{
int a, b, c, id;
bool operator < (const Node other) const {
if (a != other.a) return a < other.a;
if (b != other.b) return b < other.b;
if (c != other.c) return c < other.c;
return id < other.id;
}
}A[MAXN], B[MAXN];
int n, k;
int D[MAXM], K[MAXN], H[MAXN];
namespace BIT {
#define lb(i)(i & -i)
void modify(int x, int v) {
for (; x <= k; x += lb(x)) D[x] += v;
}
void query(int x, int &r) {
for (; x; x -= lb(x)) r += D[x];
}
}
void CDQ(int l, int r) {
if (l == r) return ;
int mid = l + r >> 1;
CDQ(l, mid); CDQ(mid + 1, r);
int i = mid + 1, j = l, tot = l;
while (i <= r && j <= mid) {
if (A[i].b >= A[j].b) //符合，考虑相等情况
BIT :: modify(A[j].c, 1), B[tot ++] = A[j ++];
else
BIT :: query(A[i].c, K[A[i].id]), B[tot ++] = A[i ++];//k数组没有顺序问题，只是一个容器
}
while (j <= mid) BIT ::modify(A[j].c, 1), B[tot ++] = A[j ++];//注意到，左半部分只会加1，所以清零时免得清成负数
while (i <= r) BIT :: query(A[i].c, K[A[i].id]), B[tot ++] = A[i ++];//剩下的都是可以
for (int i = l; i <= mid; i ++) BIT :: modify(A[i].c, -1);
for (int i = l; i <= r; i ++) A[i] = B[i];
}
int main () {
ios :: sync_with_stdio(false); cin.tie(NULL);
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> A[i].a >> A[i].b >> A[i].c, A[i].id = i;
sort(A + 1, A + 1 + n);
CDQ(1, n);
sort(A + 1, A + 1 + n);
for (int i = n; i >= 1; i --) {
if (A[i].a == A[i + 1].a && A[i].c == A[i + 1].c && A[i].b == A[i + 1].b) //完全一样
K[A[i].id] = K[A[i + 1].id];
//排序之后，相等的数肯定是连在一起的
//对一维排序的原因是让i的符合条件的j都在i的左边，相等的情况j在i的右边我们统计不到，但是最后的那个数一定正确
H[K[A[i].id]] ++;
}
for (int i = 0; i < n; i ++) cout << H[i] << '\n';
return 0;
}
更高维的偏序
以四维偏序为例，我们按第一关键字排序
给第二关键字cdq时，我们发现第一维被打乱了
但是我们只需要的知道他在左边还是右边，所以我们就可以记录第一维的 \(LEFT\) 和 \(RIGHT\)。
再对第三位进行cdq，第四维用树状数组维护即可
偏序的时间复杂度
用主定理可以求解
逆序对是 \(\mathcal{O}(N\log n)\)
三维偏序是 \(\mathcal{O}(N\log ^2n)\)
\(k\) 维偏序时 \(\mathcal{O}(N\log^{k-1}n)\)
\(\mathcal{Part}\) 11. 尾声
算法思想多加练习即可
标签：cnt,le,思想,int,mid,算法,数组,mathcal From： https://www.cnblogs.com/Phrvth/p/17300594.html