1. 单调栈

给定一个长度为 \(n\) 的数列 \(a\)，对每个数字求出其右/左边第一个值大于等于它的数字的位置。

考虑从左到右扫整个序列，维护一个栈，里面存放可能成为答案的数字，当遍历到一个新的数 \(a_i\) 的时候，可以发现栈中 \(\leq a_i\) 的数就再也不可能成为答案了，那就把它们弹掉，此时栈顶就是答案，之后加入 \(a_i\)。

由于栈中的元素是单调不升的，故得名单调栈。

这么做的复杂度：每个元素只会入栈出栈一次，所以复杂度是线性的。

Rep(i,n,1)
{
	while(top>0&&a[s[top]]<=a[i]) top--;
	ans[i]=s[top];
	s[++top]=i;
}

最大值求和

给出一个 \(n\) 个数的序列，对所有 \(1 \leq l \leq r \leq n\) 求 \(\max(a_l,a_{l+1},\dots ,a_{r-1},a_r)\) 并求和。\(n \leq 10^6,a_i \leq 10^3\)。

考虑一个数字会在哪些区间被算到，对于一个数字 \(a_p\)，用单调栈求出左面和右面第一个比它大的位置 \(l_p\) 和 \(r_p\)，那么当 \(l_p < L \leq p \leq R < r_p\) 的时候，区间 \([L,R]\) 的 \(\max\) 就是 \(a_p\)，依据乘法原理，\(a_p\) 的贡献就是 \(a_p \times (p-l_p) \times (r_p-p)\)，求和即可。

注意序列中有相同数字的时候，要钦定（比如）左边的比右边的大。

序列最大价值

给出一个 \(n\) 个数字的序列，求 \(1\leq l \leq r\leq n\) 使得 \((r-l+1) \times \min(a_l,a_{l+1},\dots ,a_{r-1},a_r)\) 最大。\(n \leq 10^6,a_i \leq 10^3\)。

还是和刚才一样对每个数字维护其在哪个极大区间成为最小值，然后算一算即可。

洛谷 P4147 玉蟾宫

有一个矩阵，每个位置是 \(0\) 或者 \(1\)。求最大的全 \(1\) 子矩阵。\(n \times m \leq 10^6\)。

枚举每一行，对每个位置维护其向上极长的 \(1\) 的段的长度，然后每行转化为刚刚那个问题即可。

2. 单调队列

有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

沿用单调栈的思路，从左到右扫描每一个 \(i\)，从栈顶弹数，不过由于栈底的数有可能不在滑动窗口里了，所以还要从栈底弾掉，栈不支持此操作，考虑使用队列。复杂度 \(\mathcal{O}(n)\)。

l=1,r=0;
For(i,1,n)
{
	while(l<=r&&a[q[r]]<=a[i]) r--;
	q[++r]=i;
	while(l<=r&&i-q[l]>=k) l++;
	if(i>=k) cout<<a[q[l]]<<" "; 
}

3. 二维前缀和

给你一个 \(n\) 行 \(m\) 列的矩阵 \(a\)。接下来有 \(q\) 次查询，给定参数 \(x_1,y_1,x_2,y_2\)。请输出以 \((x_1, y_1)\) 为左上角, \((x_2,y_2)\) 为右下角的子矩阵的和。

设 \(b_{i,j}\) 为 \((1,1)\sim (i,j)\) 这个矩阵的和，由容斥原理，可得递推式 \(b_{i,j}=b_{i-1,j}+b_{i,j-1}-b_{i-1,j-1}+a_{i,j}\)。

如果要求 \((x_1,y_1)~(x_2,y_2)\) 的矩阵和，那么 \(ans=b_{x_2,y_2}-b_{x_1-1,y_2}-b_{x_2,y_1-1}+b_{x_1-1,x_2-1}\)。

4. 二维差分

给你一个 \(n\) 行 \(m\) 列的矩阵 \(b\)。\(q\) 次操作，每次给定参数 \(x1,y1,x2,y2,v\)，将子矩阵 \((x_1,y_1)\sim (x_2,y_2)\) 加上 \(v\)，最后输出矩阵 \(b\)。

由于前缀和和差分是互逆运算，设 \(a\) 为 \(b\) 的差分数组，对前缀和的递推式做代数变换可得 \(a_{i,j}=b_{i,j}+b_{i-1,j-1}-b_{i-1,j}-b_{i,j-1}\)。

将子矩阵 \((x_1,y_1)\sim (x_2,y_2)\) 加上 \(v\)，其实就等价于

最后对于 \(a\) 数组做一遍前缀和就可以得到 \(b\) 数组了。

二维前缀和/差分看起来很麻烦但其实画个图很好理解。

5. 基数排序

首先要知道计数排序。其实就是把一个 \(\texttt{int}\) 类型的数拆成低 \(16\) 位和高 \(16\) 位，然后先对低 \(16\) 位做计数排序，再排高 \(16\) 位就行了，复杂度 \(\mathcal{O}(n+32768)\)。

对于 \(\texttt{long long}\) 类型也是一样的原理。

6. 堆

可以再 \(\mathcal{O}(\log n)\) 的时间内支持删除，插入，查询最值操作，一般用 STL 中的优先队列实现。

堆排序

把所有数字 \(\texttt{push}\) 进去然后依次 \(\texttt{pop}\) 出来即可。

时间复杂度 \(\mathcal{O}(n \log n)\)。

洛谷 P3871 [TJOI2010] 中位数

每次插入一个数字，然后询问所有数字的中位数。

维护一个大根堆一个小根堆，使得大根堆维护的是前一半的元素，小根堆维护剩下的。每次插入视情况放到小根堆/大根堆里面。

#include<bits/stdc++.h>
using namespace std ;
#define ull unsigned long long
#define ll long long
#define db double
#define random(a,b) (rand()%((b)-(a)+1)+(a))
#define se second
#define fi first
#define pr pair<int,int>
#define pb push_back
#define ph push
#define ft front
#define vec vector
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,a,b) for(int i=a;i>=b;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define NO cout<<"NO"<<"\n";
#define YES cout<<"YES"<<"\n";
#define No cout<<"No"<<"\n";
#define Yes cout<<"Yes"<<"\n";
#define str string
const int N=1e5+10;
int T,n,a,m;
struct Less
{
	int h[N],cnt,sz;
	void up(int p)
	{
		for(;p>1&&h[p]<h[p>>1];p>>=1)
		{
			swap(h[p],h[p>>1]);
		}
	}
	void push(int x)
	{
		h[++cnt]=x;
		sz++;
		up(cnt);
	}
	int size()
	{
		return sz;
	}
	int top()
	{
		return h[1];
	}
	void down()
	{
		int s=2;
		while(s<=cnt)
		{
			if(s<cnt&&h[s|1]<h[s]) s++;
			if(h[s]<h[s>>1])
			{
				swap(h[s],h[s>>1]);
				s<<=1;
			}
			else break;
		}
	}
	void pop()
	{
		h[1]=h[cnt--];
		down();
		sz--;
	}
}q1;
struct Greater
{
	int h[N],cnt,sz;
	void up(int p)
	{
		for(;p>1&&h[p]>h[p>>1];p>>=1)
		{
			swap(h[p],h[p>>1]);
		}
	}
	void push(int x)
	{
		h[++cnt]=x;
		sz++;
		up(cnt);
	}
	int size()
	{
		return sz;
	}
	int top()
	{
		return h[1];
	}
	void down()
	{
		int s=2;
		while(s<=cnt)
		{
			if(s<cnt&&h[s|1]>h[s]) s++;
			if(h[s]>h[s>>1])
			{
				swap(h[s],h[s>>1]);
				s<<=1;
			}
			else break;
		}
	}
	void pop()
	{
		h[1]=h[cnt--];
		down();
		sz--;
	}
}q2;
void Push(int x)
{
	if(!q1.size()&&!q2.size())
	{
		q1.push(x);
		return;
	}
	else if(!q2.size())
	{
		q2.push(x);
		if(q1.top()<q2.top())
		{
			swap(q1.h[1],q2.h[1]);
		} 
		return;
	}
	else if(x>=q1.top())
	{
		q1.push(x);
		if(abs(q1.size()-q2.size())>1)
		{
			q2.push(q1.top());
			q1.pop();
		}
		return;
	}
	else
	{
		q2.push(x);
		if(abs(q1.size()-q2.size())>1)
		{
			q1.push(q2.top());
			q2.pop();
		}
	}
}
int mid()
{
	if((q1.size()+q2.size())&1)
	{
		return q1.size()>q2.size()?q1.top():q2.top();
	}
	else return q2.top();
}
void solve()
{
    cin>>n;
    For(i,1,n)
    {
    	cin>>a;
    	Push(a);
	}
	cin>>m;
	while(m--)
	{
		str opt;
		cin>>opt;
		if(opt=="mid")
		{
			cout<<mid()<<"\n";
		}
		else
		{
			cin>>a;
			Push(a);
		}
	}
}
int main ( )
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    srand(time(0));
//    cin >> T ;
//    while ( T -- )
		solve();
	return 0;
}

洛谷 P1631 序列合并

有两个长度为 \(N\) 的单调不降序列 \(A,B\)，在 \(A,B\) 中各取一个数相加可以得到 \(N^2\) 个和，求这 \(N^2\) 个和中最小的 \(N\) 个。

令 \(c_{i,j}=A_i \times B_j\)。维护一个堆，第 \(1\) 大的数一定是 \(c\) 中第一列的数，所以将这 \(N\) 个数压入堆中，取出堆中的最大值是 \(c_{i,j}\)，那么 \(c_{i+1,j}\) 也可能成为答案，加入堆中，重复 \(N\) 次即可。

洛谷 P1090 [NOIP2004 提高组] 合并果子

有 \(n\) 堆石子，每次你可以选择任意不同的两堆合并，代价是两堆石子的个数之和。求合并成一堆的最小代价。

考虑贪心，每次取两堆最小的石子合并，将新的石子堆放回，递归成为一个 \(i-1\) 的问题，考虑用堆优化，时间复杂度 \(\mathcal{O}(n \log n)\)。

洛谷 P2672 [NOIP2015 普及组] 推销员

一条街上有n个白点，坐标依次是 \(x_1 \sim x_n\)，有个人一开始在 \(0\)。选择第 \(i\) 个点涂黑要付出 \(a_i\) 的代价（必须走到这个点）。最后必须回到 \(0\)。选出某k个点涂黑的代价是这 \(k\) 个点的 \(a\) 的和，加上两倍的坐标最大值。

对每个 \(k=1 \sim n\) 求，涂黑恰好 \(k\) 个不同的点的最大代价。

猜一个结论，\(k=i\) 的答案一定是在 \(k=i-1\) 的最优解的基础上再选一个最优的点得来的，发现是对的，那么就可以写出 \(\mathcal{O}(n^2)\) 的暴力。

考虑优化。预处理一个 \(pre\) 数组，\(pre_i\) 表示 \(i \sim n\) 中选择一个新的最远点可以得到的最大值。假设现在要求 \(k=i\) 的答案，\(k=i-1\) 时选择的最远点的位置是 \(pos\)，分类讨论:

• 如果要在 \(pos\) 右边选点，那么答案就是 \(pre_{pos+1}\)。
• 如果在左边选点，那么就要遍历 \(1 \sim pos-1\) 查找 \(a_i\) 最大的点，这可以用堆优化，那么答案就是堆顶元素。

将左右两边的答案比较一下如果左边的更大，那就选左边的，将堆顶元素删去即可，否则选右边的，此时最远点发生了变化，那么就要把 \(pos+1 \sim pos'-1\) 的元素入队，就做完了。

7. 并查集

每次合并两个不相交集合，或者询问两个元素是否在同一个集合里。

洛谷 P1197 [JSOI2008] 星球大战

给一张图，每次删掉一个点及相连的边，求剩下的图中的联通块数。

我们倒着从空图往回做，就变成了加边求联通块数的问题。

洛谷 P1525 [NOIP2010 提高组] 关押罪犯

有一张图，边有边权。你要给每个点确定是黑色或者白色，使得两端颜色相同的边的边权最大值最小。

solution 1

一个直观想法是尽可能让边权大的边，两端颜色不同。因此我们从大到小加边，由于不能确定两端点是什么颜色，考虑用并查集维护一个相对关系，就是敌人的敌人是朋友这种感觉，如果一条边两端点在同一集合，直接输出即可。

solution 2

考虑二分，假设二分到一个 \(\texttt{mid}\)，如果大于 \(\texttt{mid}\) 的边构成一个二分图就是可行的。

P2024 [NOI2001] 食物链

有三种生物 \(A,B,C\)，其中 \(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。
有 \(n\) 个生物，每个要么是 \(A\)，要么 \(B\)，要么 \(C\)。
每次告诉你谁吃谁或者谁和谁同类，或者问你谁吃谁/谁和谁同类是否一定不成立。

使用带权并查集，维护节点 \(x\) 与其父亲 \(fa\) 的关系，记为 \(d_x\)：

• 如果 \(d_x=0\)，那么 \(x\) 与其父亲 \(fa\) 是同类。
• 如果 \(d_x=1\)，那么 \(x\) 吃 \(fa\)。
• 如果 \(d_x=2\)，那么 \(x\) 被 \(fa\) 吃。

一些神奇的性质就是：

• \(A \stackrel{s_1}{\longrightarrow} B \stackrel{s_2}{\longrightarrow} C \Rightarrow A \stackrel{s_1+s_2}{\longrightarrow} C\)
• \(A \stackrel{s_1}{\longrightarrow} B \Rightarrow B \stackrel{-s_1}{\longrightarrow} A\)

（以上运算都是在模 \(3\) 意义下进行的）

之后再合并/路径压缩的时候用上述性质讨论一下就可以了，不再赘述。

P8779 [蓝桥杯 2022 省 A] 推导部分和

有一列数字，每次告诉你一个区间的和，或者问能否确定一个区间的和。

考虑两两元素之间的缝隙，共有 \(n+1\) 个缝隙（加上第一个元素之前的和第 \(n\) 个元素之后的）。依次编号，告诉你一个区间的和本质上就是在讲从一个缝隙走到另一个缝隙的距离。例如 \(l \sim r\) 的和是 \(s\) 就是第 \(l\) 个缝隙到 \(r+1\) 个缝隙的距离是 \(s\)。考虑带权并查集，与上一题的做法基本类似。

将某些区间问题视作关于缝隙的图是一类特殊技巧，有必要掌握一下。

8. 数论基础

在讲课的基础上添加了一些内容，就当梳理一下数论知识了。

8.1 质数

一个大于 \(1\) 的自然数，除了 \(1\) 和它自身外，不能被其他自然数整除的数叫做质数。

8.1.1 质数判定

• 若一个正整数 \(n\) 是合数，则有一个能整除 \(n\) 的数 \(t\)，其中 \(2 \leq t \leq \sqrt{n}\)

所以只需要枚举 \(2 \sim \sqrt{n}\) 的所有整数，如果能整除 \(n\)，就是合数，否则就是质数

8.1.2 筛法

求 \(1 \sim n\) 中的所有质数

8.1.2.1 埃拉托斯特尼筛法

从小到大枚举每一个数 \(x\)，考虑标记每一个合数，如果 \(x\) 没被标记，那么它就是质数，所以 \(x \times i\) 就是合数，将它们标记，由于小于 \(x^2\) 的 \(x\) 的倍数之前已经筛过了，所以从 \(x^2\) 开始。最后没被标记的就是质数，复杂度 \(\mathcal{O}(n \log n \log n)\)。

这种筛法可以进行优化，例如枚举到 \(\sqrt{n}\)，只筛奇数，bitset 优化等等，甚至可以快过线性筛法。

bitset<N> not_prime;
not_prime[1]=1;
for(int i=2;i*i<=n;i++)
{
   if(not_prime[i]==0)
	{
		for(int j=i*i;j<=n;j+=i)
		{
			not_prime[j]=1;
		}
	}
}
For(i,1,n)
{
	if(!not_prime[i]) prime[++cnt]=i;
}

8.1.2.2 欧拉筛

埃氏筛法会将一个合数重复多次标记。如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 \(\mathcal{O}(n)\) 了。

考虑让每一个合数只被其最小质因子标记。还是从小到大枚举每一个数 \(i\)，标记每一个合数，维护一个质数的集合 \(p\)，如果 \(i\) 没被标记，那么将它加入这个集合，接下来遍历这个集合（无论 \(i\) 是不是一个质数），标记 \(i \times p_j\) 为合数，如果 \(i\) 是 \(p_j\) 的倍数，那么就可以直接 \(\texttt{break}\) 了，这是由于

约数

如果 \(m\) 是 \(a\) 的因数，记作 \(m \mid a\)。

如果 \(a \mid b\) 并且 \(a \mid c\)，那么 \(a \mid (bx+cy)\)

算数基本定理

如果 \((a,b)=1\)，那么称作 \(a\) 和 \(b\) 互质

\(\operatorname{lcm}(a,b)\) 记为 \([a,b]\)。

\([a,b]=\frac{a \times b}{(a,b)}\)

最大公约数

记 \(\gcd(a,b)\) 为 \((a,b)\)。

显然 \(d \mid (a,b)\) 等价于，\(d \mid a\) 且 \(d \mid b\)

显然 \((a,b)=(a+b,b)=(a-b,b)=(a \bmod b,b)\)

取模

同余：如果 \(a\) 和 \(b\) 对 \(m\) 取模得到的结果相同，那么说 \(a\) 和 \(b\) 在模 \(m\) 意义下相等，或者说二者同余，记作 \(a \equiv b \pmod {m}\)