2025.5.1

## 数据结构专题

### 上午

先讲的基础数据结构名称？

easy，不写了。

#### 队列

数组进化 $1$。

一个有两头的排列，一头出，一头进。

出的顺序和入的顺序保持一致，简称先进先出。(FIFO)

**实现 $1$(STL)：**

直接拿c++内部的队列。

```cpp
#include<bits/stdc++.h>

#define int long long
#define pii pair<int,int>

using namespace std;

signed main(){
	queue<int> q;
	//int表示队列里的元素类型。 
	q.push(233);
	q.push(233333);
	q.push(23333333333333);
	q.pop();//删除队列头元素。(233) 
	q.push(233333333);
	int x=q.front();//获取头元素。 
	cout<<x<<'\n';//233333 
	cout<<q.size()<<'\n';//剩余元素个数。 
	return 0;
}
```

**实现 $2$ (手写):**

思想：用结构体存储各种信息。

```cpp
struct QUEUE{
	int a[maxn];//存储队列元素。 
	int st,en;//存储头and尾。 
	void push(int x){
		a[++en]=x;
	}
	void pop(){
		st++;
	}
	int size(){
		return en-st+1;
	}
	int front(){
		return a[st];
	}
}q;
```

### 另外拓展：输出问题。

endl巨慢！！！！！！！！！！！！！！！！！！！！

不用。

这里我们用往文件里输出 $10^7$ 个数并换行作为实验。

$cout+endl:14.08 sec$

$cout+"\n":0.9579sec$

结果显而易见。

## 栈：

类似垃圾桶。

与队列相反，先进后出。(FILO)

还是两种写法。

省略代码(一种STL,手写维护 $top$ 即可。)

# 作用：

$dfs$ 用栈(递归)。

$bfs$ 用队列。

### trick:单调队列。

主要思想：不断把一个数 $push$ 进去，然后看是否单调。可以拿 $deque$ 实现，但是有点 $man$。最好手写。

code:
```cpp
#include<bits/stdc++.h>

#define int long long
#define pii pair<int,int>

using namespace std;

const int maxn=2e6+5;

int a[maxn],n,k;

int q[maxn];//存储编号。

int l=1,r;

void push(int x){//插入下标为i的元素，保证单调递增。
	while(q[l]<=x-k&&r>=l)l++;
	while(a[q[r]]>=a[x]&&r>=l)r--;
	q[++r]=x;
	if(x>=k){cout<<a[q[l]]<<" ";}
}
void push2(int x){
	while(q[l]<=x-k&&l<=r)l++;
	while(a[q[r]]<=a[x]&&l<=r)r--;
	q[++r]=x;
	if(x>=k)cout<<a[q[l]]<<" ";
}

signed main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		push(i);
	}
	cout<<'\n';
	l=1,r=0;
	for(int i=1;i<=n;i++){
		push2(i);
	}
	return 0;
}
```

### 堆：

支持：插入。删除最小/大值，查询最小/大值。

另外，如果把结构体放到堆里，只能重载小于号。

**重点重点重重点：手写堆。**

思想：完全二叉树。

一些性质：

一个节点，有右儿子就有左儿子。

$节点x$ 左儿子 $2x$，右儿子 $2x+1$，父亲 $x/2$。

加一个数可能不满足性质，所以不断往上跳即可。

```cpp
struct heap{
	int a[233];//存储元素。
	int n=0;//大小。
	int top(){
		return a[1];
	} 
	void push(int x){//O(log n)
		a[++n]=x;
		int now=n;
		while(now!=1&&a[now]>a[now>>1]){//卡常 
			swap(a[now],a[now>>1]);
			now=(now>>1);
		}
	}
	void pop(){
		swap(a[1],a[n]),n--;
		int now=1;
		while((now<<1)<=n){
			int ls=now<<1;
			int rs=ls|1;
			int ms;
			if(a[rs]>a[ls]&&rs<=n)ms=rs;
			else ms=ls;
			if(a[ms]>a[now]){
				swap(a[ms],a[now]);
				now=ms;
			}
			else break;
		}
	}
	int size(){
		return n;
	}
}h; 
```

## 并查集

路径压缩：在找根的过程中记录 $to$ 数组。

钟神随机化：假的，不写。

```cpp
int go(int x){
	if(x==to[x])return x;
	return to[x]=go(to[x]);
}
```

## 分块：

把一个序列分成若干块，每块元素数量类似，约为 $\sqrt n$ 个，这样可以最小化时间复杂度。

分块线段树 $1$ ：

维护每个块的和以及元素数量。

```cpp
#include<bits/stdc++.h>

#define int long long
#define pii pair<int,int>

using namespace std;

int n,m;
const int maxn=1e6+5;
int a[maxn];
int cnt[maxn],belong[maxn];
int sum[maxn];
int lz[maxn];
signed 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-1)/s+1;
	}
	for(int i=1;i<=n;i++){
		cnt[belong[i]]++;
		sum[belong[i]]+=a[i];
	}
	for(int i=1;i<=m;i++){
		int op;
		cin>>op;
		if(op==1){
			int x,y,v;
			cin>>x>>y>>v;
			if(belong[x]==belong[y]){
				for(int i=x;i<=y;i++){
					sum[belong[i]]+=v,a[i]+=v;
				}
			}
			else{
				for(int i=x;belong[i]==belong[x];i++){
					a[i]+=v;
					sum[belong[i]]+=v;
				}
				for(int i=y;belong[i]==belong[y];i--){
					a[i]+=v;
					sum[belong[i]]+=v;
				}
				for(int i=belong[x]+1;i<belong[y];i++){
					sum[i]+=v*cnt[i];
					lz[i]+=v;
				}
			}
		}
		else{
			int x,y;
			cin>>x>>y;
			if(belong[x]==belong[y]){
				int ans=0;
				for(int i=x;i<=y;i++){
					ans+=a[i]+lz[belong[i]];
				}
				cout<<ans<<'\n';
			}
			else{
				int ans=0;
				for(int i=x;belong[i]==belong[x];i++){
					ans+=a[i]+lz[belong[i]];
				}
				for(int i=y;belong[i]==belong[y];i--){
					ans+=a[i]+lz[belong[i]];
				}
				for(int i=belong[x]+1;i<belong[y];i++){
					ans+=sum[i];
				}
				cout<<ans<<'\n';
			}
		}
	}
	return 0;
}
```

线段树2:

维护两个标记，类似。

```cpp
#include<bits/stdc++.h>

#define int long long
#define pii pair<int,int>

using namespace std;

const int maxn=1e6+5;

int a[maxn];
int n,q,mod;
int belong[maxn];
int lz_add[maxn], lz_mul[maxn];
int cnt[maxn], sum[maxn];

signed main(){
    cin >> n >> q >> mod;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] %= mod;
    }
    
    int s = sqrt(n);
    for(int i = 1; i <= n; i++){
        belong[i] = (i-1)/s + 1;
        cnt[belong[i]]++;
        sum[belong[i]] = (sum[belong[i]] + a[i]) % mod;
    }
    
    int blocks = belong[n];
    for(int i = 1; i <= blocks; i++){
        lz_add[i] = 0;
        lz_mul[i] = 1;
    }
    
    while(q--){
        int op;
        cin >> op;
        if(op == 1){
            int x, y, k;
            cin >> x >> y >> k;
            k %= mod;
            int bx = belong[x], by = belong[y];
            if(bx == by){
                for(int i = x; i <= y; i++){
                    sum[bx] = (sum[bx] - a[i] + mod) % mod;
                    a[i] = (a[i] * k) % mod;
                    sum[bx] = (sum[bx] + a[i]) % mod;
                }
            }
            else{
                for(int i = x; belong[i] == bx; i++){
                    sum[bx] = (sum[bx] - a[i] + mod) % mod;
                    a[i] = (a[i] * k) % mod;
                    sum[bx] = (sum[bx] + a[i]) % mod;
                }
                for(int i = y; belong[i] == by; i--){
                    sum[by] = (sum[by] - a[i] + mod) % mod;
                    a[i] = (a[i] * k) % mod;
                    sum[by] = (sum[by] + a[i]) % mod;
                }
                for(int i = bx + 1; i < by; i++){
                    sum[i] = (sum[i] * k) % mod;
                    lz_mul[i] = (lz_mul[i] * k) % mod;
                    lz_add[i] = (lz_add[i] * k) % mod;
                }
            }
        }
        else if(op == 2){
            int x, y, k;
            cin >> x >> y >> k;
            k %= mod;
            int bx = belong[x], by = belong[y];
            if(bx == by){
                for(int i = x; i <= y; i++){
                    sum[bx] = (sum[bx] + k) % mod;
                    a[i] = (a[i] + k) % mod;
                }
            }
            else{
                for(int i = x; belong[i] == bx; i++){
                    sum[bx] = (sum[bx] + k) % mod;
                    a[i] = (a[i] + k) % mod;
                }
                for(int i = y; belong[i] == by; i--){
                    sum[by] = (sum[by] + k) % mod;
                    a[i] = (a[i] + k) % mod;
                }
                for(int i = bx + 1; i < by; i++){
                    sum[i] = (sum[i] + k * cnt[i]) % mod;
                    lz_add[i] = (lz_add[i] + k) % mod;
                }
            }
        }
        else if(op == 3){
            int x, y;
            cin >> x >> y;
            int bx = belong[x], by = belong[y];
            int ans = 0;
            if(bx == by){
                for(int i = x; i <= y; i++){
                    ans = (ans + a[i] * lz_mul[bx] + lz_add[bx]) % mod;
                }
            }
            else{
                for(int i = x; belong[i] == bx; i++){
                    ans = (ans + a[i] * lz_mul[bx] + lz_add[bx]) % mod;
                }
                for(int i = y; belong[i] == by; i--){
                    ans = (ans + a[i] * lz_mul[by] + lz_add[by]) % mod;
                }
                for(int i = bx + 1; i < by; i++){
                    ans = (ans + sum[i]) % mod;
                }
            }
            cout << ans % mod << '\n';
        }
    }
    return 0;
}
```

## 0/1Trie 树：

例题 p10471:

考虑异或的性质。

只有不同位置才能产生贡献。

0/1 Trie 维护即可。

```cpp
#include<bits/stdc++.h>

#define int long long
#define pii pair<int,int>

using namespace std;

int n;
const int maxn=1e5+5;
int a[maxn];
int ne[maxn][2];
int cnt=0;
void insert(int x){
	int p=0;
	for(int i=30;i>=0;i--){
		int k=(x>>i)&1;
		if(!ne[p][k]){
			ne[p][k]=++cnt;
		}
		p=ne[p][k];
	}
}
int query(int x){
	int p=0,ans=0;
	for(int i=30;i>=0;i--){
		int k=(x>>i)&1;
		if(ne[p][k^1]){
			p=ne[p][k^1];
			ans|=(1<<i);
		}
		else p=ne[p][k];
	}
	return ans;
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		insert(a[i]);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		ans=max(ans,query(a[i]));
	}
	cout<<ans;
	return 0;
}

```