4-1

# 队列
代码：

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

using namespace std;

queue<int> q;
//queue<队列里面的元素类型> 变量名;

int main()
{
	q.push(233);
	q.push(2233);//向队列里面加入一个元素
	q.pop();//从队列中删除一个元素 删除是队列头的元素 233 void类型没有返回值
	int x = q.front();//获取队列头元素 2233
	cout << q.size() << endl;//获取队列剩余的元素个数 1 
}

```
# 栈
代码：
```cpp
#include<stack>
//#include<bits/stdc++.h>

using namespace std;

stack<int> q;
//stack<队列里面的元素类型> 变量名;

int main()
{
	q.push(233);
	q.push(2233);//向栈里面加入一个元素
	q.pop();//从栈中删除一个元素 删除是队列头的元素 2233 void类型没有返回值
	int x = q.top();//获取栈顶部元素 233
	cout << q.size() << endl;//获取栈剩余的元素个数 1 
}

```
# 队列
代码：

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

using namespace std;

struct queue
{
	int a[1000];
	int head=1;//队列头在哪里 
	int tail=0;//队列尾巴在哪里 
	void push(int x)
	{
		tail ++;
		a[tail] = x;
	}
	void pop()
	{
		head++;
	}
	int size()
	{
		return tail-head+1;
	}
	int front()
	{
		return a[head];
	}
}q;

```
# 双端队列
代码：

```cpp
#include<deque>

using namespace std;

deque<int> q;//双端队列 
//q.push_front() 从前面加入
//q.pop_front() 从前面删除
//q.front() 询问前面的数是多少
//q.push_back() 从后面加入
//q.pop_back() 从后面删除
//q.back() 询问后面的数是多少

int a[maxn];

void push(int i)//单调队列的插入 插入下标为i的元素 要保证队列单调递增
{
	while (q.size() > 0 && a[q.back()] >= a[i])
		q.pop_back();
	q.push_back(i);
}

int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	cin >> m;//所有长度为m的区间的最小值
	for (int i=1;i<=n;i++)
	{
		push(i);//向单调队列里面加入a[i]这个元素
		if (i-m == q.front()) q.pop_front();//把a[i-m]这个数删掉 
		if (i>=m)//区间长度已经超过m了 需要取出最小值
			cout << a[q.front()] << "\n";
	} 
		
}

```
# 双指针
代码：

```cpp
int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	cin >> m;
	
	int sum=0;
	for (int l=1,r=1;l<=n;sum-=a[l],l++)
	{
		while (sum<=m && r<=n)
		{
			sum += a[r];
			r++;
		}
		if (sum>m)
		{
			r--;
			sum -= a[r];
		}
		ans = max(ans,r-l);//a[l] ~ a[r-1]
	}
}

```
# 堆
代码：
```cpp
#include<queue>
//#include<bits/stdc++.h>

using namespace std;

priority_queue<int> q;
//大根堆 
//小根堆最简单的方法：取负号

struct rec
{
	int a,b;
};
//如果要把结构体 放入 stl比大小 只能重载小于号 
bool operator<(const rec &x,const rec &y)
{
	return x.a + x.b > y.a + y.b;
}

priority_queue<rec> qq;//取出a+b最小的结构体

int main()
{
	q.push(233);
	q.push(2233);//向堆里面加入一个元素
	q.pop();//从堆中删除一个元素 删除是堆中最大的元素 2233 void类型没有返回值
	int x = q.top();//获取堆中最大元素 233
	cout << q.size() << endl;//获取堆剩余的元素个数 1 
}

```
# 手写堆
代码：
```cpp
struct heap
{
	int a[1010];//堆的每一个元素 
	int n=0;//堆有几个元素	
	
	int top()//询问最大值 
	{
		return a[1];
	}
	void push(int x)//插入一个数
	{//O(logn)
		n++;a[n] = x;
		int p=n;
		while (p!=1)
		{
			if (a[p] > a[p>>1])
			{
				swap(a[p],a[p>>1]);
				p = 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;//p*2+1
			int pp=l;
			if (r<=n && a[r] > a[l]) pp=r;//pp一定是两个儿子中较大的那个 
			if (a[pp] > a[p])
			{
				swap(a[pp],a[p]);
				p=pp;
			}
			else
			{
				break;
			}
		}
	}
	int size()//询问还有几个数
	{
		return n;
	} 
};

```
# 例题
## 一：AC CODE

```cpp
#include <queue>
#include <iostream>
#include <algorithm>
#define a first
#define b second
#define pii std::pair<int, int>

using std::cin;
using std::cout;
using std::priority_queue;
const int K = 60;

priority_queue<pii> p;
priority_queue<int> q[K];

int main()
{
	int k;
	cin >> k;
	for (int i = 1; i <= k; ++i)
	{
		int n;
		cin >> n;
		for (int j = 1; j <= n; ++j)
		{
			int a;
			cin >> a;
			q[i].push(a);
		}
	}
	for (int i = 1; i <= k; ++i)
	{
		if (q[i].size() > 0)
			p.push({q[i].top(), i});
	}
	while (p.size() >= 3)
	{
		auto f = p.top();
		p.pop();
		auto s = p.top();
		p.pop();
		auto t = p.top();
		p.pop();
		if (s.first + t.first <= f.first)
		{
			int id = f.b;
			q[id].pop();
			if (q[id].size() > 0)
				p.push({id, q[id].top()});
		}
		else
		{
			cout << f.b << ' ' << f.a << ' ' << s.b << ' ' << s.a << ' ' << t.b << ' ' << t.a << '\n';
			return 0;
		}
		p.push(s);
		p.push(t);
	}
	cout << "NIE" << '\n';
	return 0;
}

```
# 并查集
代码：

```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 7;

int read()
{
	int x = 0, w = 1;
	char ch = getchar();
	while(ch > '9' || ch < '0')
	{
		if(ch == '-')
		{
			w = -1;
			ch = getchar();
		}
	}
	while(ch <= '9' && ch >= '0')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * w;
}

long long Qmi(int a, int b, int p)
{
	if(b == 0)
	{
		return 1%p;
	}
	
	if(b == 1)
	{
		return a%p;
	}
	
	long long ans = Qmi(a, b/2, p);
	
	ans = ans*ans%p;
	
	if(b % 2)
	{
		ans = ans*a%p;
	}
	
	return ans % p;
}

bool isprime(long long x)
{
	if(x <= 1)
	{
		return false;
	}
	if(x == 2)
	{
		return true;
	}
	if(x % 2 == 0)
	{
		return false;
	}
	for(int i = 3;  i <= sqrt(x);  i += 2)
	{
		if(x % i == 0)
		{
			return false;
		}
	}
	return true;
}

int n, q;

int to[MAXN];

int go(int p)
{
	if(p == to[p])
	{
		return p;
	}
	else
	{
		return go(to[p]);
	}
}//连

int main()
{
	//freopen("qwq.in", "r", stdin);
	//freopen("qwq.out", "w", stdout);
	
	cin>>n>>q;
	//先连自己
	for(int i = 1;  i <= n;  i++)
	{
		to[i] = i;
	}
	
	while(q--)
	{
		int op;
		
		cin>>op;
		
		if(op == 1)
		{
			int x, y;
			cin>>x>>y;
			if(rand() % 2)
			{
				to[go(x)] = go(y);
			}
			else
			{
				to[go(x)] = go(y);
			}
		}
		else
		{
			int x, y;
			cin>>x>>y;
			if(go(x) == go(y))
			{
				cout<<"Y"<<'\n';
			}
			else
			{
				cout<<"N"<<'\n';
			}
		}
	}
	
	return 0;
}

```
## 例二
代码： 
```cpp
int main()
{
	cin >> n;
	for (int i=1;i<=n;i++)
		to[i] = i;
		
	for (int i=m;i>=1;i--)//倒着读 自己实现 
	{
		int l,r,x;
		//go(i) 从i向右 第一个没被染色的位置 
		cin >> l >> r >> x;//第i个操作
		
		int p = go(l);
		while (p<=r)//当前位置还在区间内
		{
			a[p] = x;//染色 
			int np = go(p+1);
			to[p] = go(r+1);
			p = np;
		} 
	} 
}

```

# Tire树（字典树
 ![演示](https://cdn.luogu.com.cn/upload/image_hosting/l1eu9m2d.png)
## 01Tire
### 复杂度$O（nlog(n))$
### 代码：

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

using namespace std;
struct node
{
	int nxt[2];
	node()
	{
		nxt[0]=nxt[1]=0;
	}
}z[23333];
void insert(int x)
{
	int p=root;
	for(int i=30;i>=0;i--)
	{
		int y=(x>>i)&1;
		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=ans|(1<<i);
			p=z[p].nxt[y^1];
			
		}
		else{
			p=z[p].nxt[y];
		}
	}
	return ans;
}
int main()
{
	root=1;
	return 0;
}

```
# 分块

# 莫队
## 莫队是由莫涛大神提出的，一种玄学毒瘤暴力骗分区间操作算法，它以简短的框架、简单易记的板子和优秀的复杂度闻名于世$ O（nlogn) $
## 基本概念
### 莫队算法的核心在于维护两个指针（左指针 $l $和右指针 $r$），通过移动这两个指针来扩展或收缩当前维护的区间，从而处理不同的查询。通过对查询进行合理排序，使得指针移动的总次数尽可能少。
## 算法流程
### 离线处理：将所有查询按照一定规则排序。通常使用分块思想，将整个区间分成若干块，先按照查询的左端点所在的块编号排序，如果左端点所在块编号相同，则按照右端点排序。
## 初始化指针：
### 初始化左指针$ l = 1$，右指针$ r = 0$，表示当前维护的区间为空。
## 处理查询：
### 按照排序后的顺序依次处理每个查询。对于每个查询$ [L, R]$，通过移动左指针 $l $和右指针$ r$ 来扩展或收缩当前维护的区间，使其与查询区间 $[L, R] $一致。在移动指针的过程中，更新维护的信息（如区间和、区间众数等）。
## 记录结果：
### 当当前维护的区间与查询区间$ [L, R]$ 一致时，记录该查询的结果。

# 分治
## 就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
## 例题三
### 归并求逆序对

```cpp
void merge(int l,int r)//要计算l~r这个区间有多少个逆序对
{
	if (l==r) return;
	int m=(l+r) >> 1;//(l+r)/2
	merge(l,m);//递归去算l~m的答案 a[l]~a[m] 排好序了 
	merge(m+1,r);//递归去算m+1~r的答案 a[m+1]~a[r] 排好序了 
	//i在左边 j在右边的答案 
	int p1 = l, p2 = m+1;
	for (int i=l;i<=r;i++)
	{
		if (p1 > m) b[i] = a[p2],p2++;
		else if (p2 > r) b[i] = a[p1],p1++; 
		else if (a[p1] <= a[p2]) b[i] = a[p1],p1++;
		else b[i] = a[p2],p2++,ans+=m-p1+1;
	}
	for (int i=l;i<=r;i++)
		a[i] = b[i]; 
}

```