2025清北学堂五一假期 CSP-S（普转提）核心算法精选营 Day1(5.1) 数据结构基础、并查集、分块、莫队、分治

**授课老师：钟皓曦**

注：本笔记未按照讲课顺序排序。

# 1.题外话：考场坑点
## 1-1.\n 还是 endl
哪个快？请看！

![1-1.\n 还是 endl](https://cdn.luogu.com.cn/upload/image_hosting/xnt02557.png "1-1.\n 还是 endl")

通过实践发现，输出 $10000000$ 个换行，使用 $\texttt{endl}$ 用了 $14.08s$，但使用换行符仅用了 $0.9579s$。

所以，前人血的教训，你学会了吗？

## 1-2.DFS 爆栈
如果深度优先搜索递归层数过多，就可能爆栈，但有时我们又需要在本地测大样例，所以我们需要用一些方法扩大栈。

具体方法见 [这里](https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=68018901_16_pg&wd=C%2B%2B%20DFS%E6%80%8E%E6%A0%B7%E6%89%A9%E5%A4%A7%E6%A0%88%E7%A9%BA%E9%97%B4&fenlei=256&rsv_pq=0xb126d64300165a22&rsv_t=f751Xk0gz9x%2B4ocmqC4paWnlg%2BWyk%2BfvBxnN9ejvnhF1piOpFQ1WhXXiIpYR&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=57&rsv_sug1=51&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&inputT=16443&rsv_sug4=17424)。

## 1-3.你会乘/除以2吗
用 $\texttt{/2}$？太慢了！用 $\texttt{>>1}$。

用 $\texttt{*2}$？太慢了！用 $\texttt{<<1}$。

# 2.数据结构基础
一个程序中，包含两大部分：算法、数据结构。其中，算法解决“怎么算”的问题，数据结构解决“怎么存”的问题。

最简单的数据结构是变量，数组是封装好的数据结构。

由数组推广，我们得到了**队列**、**栈**。

## 2-1.队列
一种**先进先出**，即 $\bm{FIFO}\texttt{(First In First Out)}$ 数据结构。

模板见 [B3616](https://www.luogu.com.cn/problem/B3616)。

```cpp
#include<bits/stdc++.h>
using namespace std;
queue<int> q;
int main(){
	int n,num,x;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&num);
		if(num==1){
			scanf("%d",&x);
			q.push(x);
		}
		else if(num==2){
			if(q.empty()){
				printf("ERR_CANNOT_POP\n");
			}
			else{
				q.pop();
			}
		}
		else if(num==3){
			if(q.empty()){
				printf("ERR_CANNOT_QUERY\n");
			}
			else{
				printf("%d\n",q.front());
			}
		}
		else{
			printf("%d\n",q.size());
		}
	}
	return 0;
}
```

## 2-2.栈
一种**先进后出**，即 $\bm{FILO}\texttt{(First In Last Out)}$ 数据结构。

模板见 [B3614](https://www.luogu.com.cn/problem/B3614)。

```cpp
#include<iostream>
#include<cstdio>
#include<stack>
#define int unsigned long long
using namespace std;
string s;
int t,n,x;
signed main(){
	scanf("%lld",&t);
	for(int i=1;i<=t;i++){
		scanf("%lld",&n);
        stack<int> st;
		for(int i=1;i<=n;i++){
			cin>>s;
			if(s=="push"){
				cin>>x;
				st.push(x);
			}
			else if(s=="pop"){
				if(st.empty()){
					printf("Empty\n");
				}
				else{
					st.pop();
				}
			}
			else if(s=="query"){
				if(st.empty()){
					printf("Anguei!\n");
				}
				else{
					cout<<st.top()<<'\n';
				}
			}
			else{
				cout<<st.size()<<'\n';
			}
		}
	}
	return 0;
} 
```

# 2-3.单调队列
两种：单调递增、单调递减。

思路基本一致，用单调递增举例。

一组数据：$1,3,-1,-3,5,3,6,7$。
- 把 $1$ 放入队列中。\
  当前队列：$1$。
- 放入 $3$，$3$ 比 $1$ 大，放入后符合单调递增，不做改动。\
  当前队列：$1,3$。
- 放入 $-1$，不满足单调递增，依次删除前面的数，直到满足单调递增为止。\
  当前队列：$-1$。
- 放入 $-3$。\
  当前队列：$-3$。
- 放入 $5$。\
  当前队列：$-3,5$。
- 放入 $3$。\
  当前队列：$-3,3$。
- 放入 $6$。\
  当前队列：$-3,3,6$。
- 放入 $7$。\
  当前队列：$-3,3,6,7$。

最终队列：$-3,3,6,7$。

$\color{red}\texttt{Code:}$

```cpp
#include<iostream>
#include<cstdio>
#define int long long
using namespace std;
int n,k,a[1000005],q[1000005],hd,tl,max_[1000005],min_[1000005];
signed main(){
	scanf("%lld %lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	hd=1;
	for(int i=1;i<=n;i++){
		while(hd<=tl&&a[q[tl]]<=a[i]){
			tl--;
		}
		tl++;
		q[tl]=i;
		while(hd<=tl&&q[hd]<=i-k){
			hd++;
		}
		if(i>=k){
			max_[i]=a[q[hd]];
		}
	}
	hd=1,tl=0;
	for(int i=1;i<=n;i++){
		while(hd<=tl&&a[q[tl]]>=a[i]){
			tl--;
		}
		tl++;
		q[tl]=i;
		while(hd<=tl&&q[hd]<=i-k){
			hd++;
		}
		if(i>=k){
			min_[i]=a[q[hd]];
		}
	}
	for(int i=k;i<=n;i++){
		printf("%lld ",min_[i]);
	}
	printf("\n");
	for(int i=k;i<=n;i++){
		printf("%lld ",max_[i]);
	}
	printf("\n");
	return 0;
} 
```

## 2-4.堆
分为小根堆、大根堆。

用 $\texttt{priority\_queue}$ 维护即可。

小根堆可以不写 $\texttt{greater<int>,vector<int>}$，可以让加入的每个数都取相反数。

某些时候，我们需要用到**手写堆**，这也为后面的知识奠定基础。

**手写堆** $\color{red}\texttt{Code:}$

```cpp
struct heap
{
    int a[1010000];
    int n=0;
    int top(){
        return a[1];
    }
    void push(int x){
        n++;
        int p=n;
        a[n]=x;
        while(p!=1){
            if(a[p]>a[p>>1]){ //用 >>1 替代 /2
                swap(a[p],a[p>>1]);
                p>>=1;
            }
            else{
                break;
            }
        }
    }
    void pop(){
        swap(a[1],a[n]);
        n--;
        int p=1;
        while((p<<1)<=n){
            int l=p<<1;
            int r=l|1;
            int now=l;
            if(r<=n&&a[r]>a[l]){
                now=r;
            }
            if(a[now]>a[p]){
                swap(a[now], a[p]);
                p = now;
            }
            else{
                break;
            }
        }
    }
    int size(){
        return n;
    }
} h;
```

### 例1.[POI 2011] PAT-Sticks
[$\texttt{P3528 [POI 2011] PAT-Sticks}$](https://www.luogu.com.cn/problem/P3528)。

~~暴力显然不行。~~

我们给每种颜色都单独开一个堆，最后用一个堆存储所有的堆的堆顶。

## 2-5.Trie 树
中文名为**字典树**，可以处理字符串问题和**区间最大异或和**问题。

### 例2.区间最大异或和
有一个序列 $a_1,a_2, \cdots ,a_n$，求两个数 $l,r$，使得 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r$ 最大。

使用 $\texttt{Trie}$ 解决。

$\color{red}\texttt{Code:}$
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=1e5+5;
struct node{
	int nxt[2];
	node(){
		nxt[0]=nxt[1]=0;
	}
} z[max_n];
int cnt,root;
void insert(int x){ //插入 
	int p=root;
	for(int i=30;i>=0;i--){
		int y=(x>>i)&1; //取 x 二进制的第 i 位
		if(z[p].nxt[y]==0){
			cnt++;
			z[p].nxt[y]=cnt;
		} 
		p=z[p].nxt[y];
	}
}
int query(int x){ //查询 
	int p=root,ans=0;
	for(int i=30;i>=0;i--){
		int y=(x>>i)&1;
		if(z[p].nxt[y^1]!=0){
			ans|=(1<<i),p=z[p].nxt[y^1];
		}
		else{
			p=z[p].nxt[y];
		}
	}
	return ans;
}
int main(){
	root=1;
	return 0;
}
```

# 3.并查集
[$\texttt{P3367 【模板】并查集}$](https://www.luogu.com.cn/problem/P3367) $\color{red}\texttt{Code:}$
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
const int max_n=2e5+5;
int n,m,fa[max_n],rk[max_n];
int find(int x){ //找x的最大祖先 
	if(x==fa[x]){
		return x;
	} 
	else{
		return fa[x]=find(fa[x]); //路径压缩
	}
}
void merge(int x,int y){ //将x与y的祖先合并 
	int fx=find(x);
	int fy=find(y);
	if(fx==fy){ //x和y就在一个集合里，无需合并 
		return;
	}
	else{ //按秩合并
		if(rk[fx]>rk[fy]){
			fa[fy]=fx;
		}
		else if(rk[fx]<rk[fy]){
			fa[fx]=fy;
		}
		else{
			fa[fx]=fy;
			rk[fy]++;
		}
	}
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++){
		fa[i]=i; //一开始一定要把父亲设为自己
	}
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d %d %d",&z,&x,&y);
		if(z==1){
			merge(x,y);
		}
		else{
			if(find(x)==find(y)){
				printf("Y\n");
			}
			else{
				printf("N\n");
			}
		}
	}
	return 0;
}
```

# 4.分块
> 知周所众，如果一个东西强于另一个东西，且这两个东西都有用的话，那么强者的用时一定大于弱者。——zhx

与线段树相比，处理的题目更多，用时自然更慢。

$\color{red}\texttt{Code:}$ $\color{red}\texttt{来自 @}$[$\texttt{MyLove\_Forever\_Math}$](https://www.luogu.com.cn/user/1208986)

```cpp
int belong[maxn]; // belong[i] 代表第i个数属于第几块
int sum[maxn];		// sum[i] 代表第i块的和是多少
int daxiao[maxn]; // daxiao[i] 代表第i块的大小是多少
int col[maxn];		// col[i] 代表第i块被整体加了col[i]
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	int s = sqrt(n); // 每块的大小
	for (int i = 1; i <= n; i++)
		belong[i] = i / s + 1;
	for (int i = 1; i <= n; i++)
	{
		sum[belong[i]] += a[i];
		daxiao[belong[i]]++;
	}
	for (int x = 1; x <= m; x++)
	{
		int opt;
		cin >> opt;
		if (opt == 1) // 询问操作
		{
			int l, r;
			cin >> l >> r;
			int ans = 0;
			if (belong[l] == belong[r])
				for (int i = l; i <= r; i++)
					ans += a[i] + col[belong[i]];
			else
			{
				for (int i = l; belong[i] == belong[l]; i++)
					ans += a[i] + col[belong[i]];
				for (int i = r; belong[i] == belong[r]; i--)
					ans += a[i] + col[belong[i]];
				for (int i = belong[l] + 1; i < belong[r]; i++)
					ans += sum[i];
			}
			cout << ans << "\n";
		}
		else
		{
			int l, r, v;
			cin >> l >> r >> v;
			if (belong[l] == belong[r])
				for (int i = l; i <= r; i++)
					a[i] += v;
			else
			{
				for (int i = l; belong[i] == belong[l]; i++)
					a[i] += v, sum[belong[i]] += v;
				for (int i = r; belong[i] == belong[r]; i--)
					a[i] += v, sum[belong[i]] += v;
				for (int i = belong[l] + 1; i < belong[r]; i++)
				{
					sum[i] += v * daxiao[i];
					col[i] += v;
				}
			}
		}
	}
	return 0;
}
```

# 5.莫队
## 例3.偶数次个数
询问 $l,r$，求 $a_l,a_{l+1}, \cdots ,a_r$ 中出现偶数次的数有几个。

大约是莫队板子。

$\color{red}\texttt{Code:}$ $\color{red}\texttt{来自 @}$[$\texttt{MyLove\_Forever\_Math}$](https://www.luogu.com.cn/user/1208986)

```cpp
#include <cmath>
#include <iostream>
#include <algorithm>

using std::cin;
using std::cout;
using std::sort;
const int N = 2e5 + 10;

int bel[N];

struct Query
{
	int l, r, id;
	friend bool operator<(const Query &a, const Query &b)
	{
		return bel[a.l] ^ bel[b.l] ? bel[a.l] < bel[b.l] : a.r < b.r;
	}
} query[N];

int len;
int ans;
int a[N];
int cnt[N];
int ans_[N];

void ins(int x)
{
	cnt[x]++;
	if (cnt[x] % 2 == 0)
		ans++;
	else if (cnt[x] != 1 && cnt[x] % 2)
		ans--;
}
void del(int x)
{
	cnt[x]--;
	if (cnt[x] != 0)
	{
		if (cnt[x] % 2 == 0)
			ans++;
		else
			ans--;
	}
}

int main()
{
	int n;
	cin >> n;
	len = sqrt(n);
	for (int i = 1; i <= n; ++i)
		bel[i] = (i - 1) / len + 1;
	for (int i = 1; i <= n; ++i)
		cin >> a[i];
	int q;
	cin >> q;
	for (int i = 1; i <= q; ++i)
	{
		int l, r;
		cin >> l >> r;
		query[i] = (Query){l, r, i};
	}
	int l = 1, r = 0;
	sort(query + 1, query + q + 1);
	for (int i = 1; i <= q; ++i)
	{
		int nowl = query[i].l;
		int nowr = query[i].r;
		int nowid = query[i].id;
		while (r < nowr)
			ins(a[++r]);
		while (r > nowr)
			del(a[r--]);
		while (l < nowl)
			del(a[l++]);
		while (l > nowl)
			ins(a[--l]);
		ans_[nowid] = ans;
	}
	for (int i = 1; i <= q; ++i)
		cout << ans_[i] << '\n';
	return 0;
}
```

# 6.分治
## 例4.逆序对
[$\texttt{P1908 逆序对}$](https://www.luogu.com.cn/problem/P1908)。

# 7.作业
- [Day1 题单](https://www.luogu.com.cn/training/757616) 在此。
- [bzoj#P2054. 疯狂的馒头](https://hydro.ac/p/bzoj-P2054)\
  ![7.题面](https://cdn.luogu.com.cn/upload/image_hosting/iw2xsnmc.png "7.题面")\
  ![7.数据范围](https://cdn.luogu.com.cn/upload/image_hosting/hfy5kx3c.png "7.数据范围")

#### 后记
更多内容，请移步至 [$\color{red}\texttt{ryf2011}$](https://www.luogu.com.cn/user/1151973 "点我进入ryf2011")。