5.1集训DAY1

# 数据结构
## 队列：FIFO(first in first out)
### std
```cpp
queue<int> q;
//queue<队列里面的元素类型> 队列名;
//q.push();插入元素
//q.pop();删除队头
//q.front();返回队头
//q.size();返回队长 
```
### 手写队列
```
const int maxn=1e5+5;
struct queue
{
	int a[maxn];
	int h=1,t=0;//h是队头,t是队尾,注意队头为1
	void push(int x)//插入元素
	{
		a[++t]=x;
	}
	void pop()//删除队头
	{
		h++;
	}
	int size()//返回队长 
	{
		return t-h+1;
	}
	int front()//返回队头
    {
		return a[h];
    }
}q;
```
## 栈：FILO(first in last out)
### std
```cpp
stack<int> q;
//stack<栈里面的元素类型> 栈名
//q.push();插入元素
//q.pop();删除栈顶
//q.top();返回栈顶
//q.size();返回栈长
```
### 手写栈
```cpp
const int maxn=1e5+5;
struct stack
{
	int a[maxn];
	int h=0;//h是队顶 
	void push(int x)//插入元素
	{
		a[++h]=x;
	}
	void pop()//删除栈顶 
	{
		h--;
	}
	int size()//返回栈长 
	{
		return h;
	}
	int top()//返回栈顶 
	{
		return a[head];
  	}
}q;
```
## 双端队列
### std
```cpp
deque<int> q;
//deque<队列里面的元素类型> 队列名;
//q.push_front();插入队头
//q.pop_front();删除队头
//q.front();返回队头
//q.push_back();插入队尾
//q.pop_back();删除队尾
//q.back();返回队尾
```
## 单调队列
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int h,r=-1,n,m,a[maxn],q[maxn];
int main()
{
	cin>>n>>m;	
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) 
	{
		if(h<=r&&i-m+1>q[h]) h++;
		while(h<=r&&a[q[r]]>=a[i]) r--;//维护最小 
		//while(h<=r&&a[q[r]]>=a[i]) r--; 维护最大 
		q[++r]=i;
		if(i>=m) cout<<a[q[h]]<<' ';//输出答案,即队首元素
	}
	return 0;
}
```
## 单调栈
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int sta[maxn],a[maxn],ans[maxn],n,top;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		while(top&&a[i]>a[sta[top]])
		{
			ans[sta[top]]=i;
			top--; 
		}
		sta[++top]=i;
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}
```
## 堆
### std
```cpp
priority_queue<int> q;
//priority_queue<堆里面的元素类型> 堆名; 
//小根堆最简单的方法：取负号 
//q.push();插入元素
//q.pop();删除堆顶
//q.top();返回堆顶
//q.size();返回堆长
```
### 手写堆
```cpp
const int maxn=1e5+5;
struct heap
{
	int a[maxn];
	int h=0;
	int top()//;返回堆顶
	{
		return a[1];
	}
	void push(int x)//插入元素
	{
		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;
			int pp=l;
			if (r<=n&&a[r]>a[l]) pp=r;
			if (a[pp]>a[p])
			{
				swap(a[pp],a[p]);
				p=pp;
			}
			else
			{
				break;
			}
		}
	}
	int size()//返回堆长
	{
		return n;
	} 
};
```
## 并查集
### 代码
```cpp
const int maxn=1e5+5;
int to[maxn];//to[i] 代表i的箭头指向谁
int go(int p)//从p点出发 看最后会走到哪里
{
	if (p==to[p]) return p;
	else 
	{
		to[p]=go(to[p]);
		return to[p];
	}
} 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) to[i]=i;//初始都指向自己 
	int p1,p2; 
	to[go(p1)]=go(p2);
	go(p1)==go(p2);
}
```
## 字典树
### 代码
```cpp
const int maxn=1e5+5;
struct node
{
	int nxt[2];//nxt[0] nxt[1] 代表从当前点走0和1会走到哪里 走到0的话代表这个节点不存在 
	node()
	{
		nxt[0] = nxt[1] = 0;
	}
}z[maxn];
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)//从trie中找一个数 使得他和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;
}
```
## 分块
### 代码
```cpp
const int maxn=1e5+5;
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;
}
```
## 分治
### 代码
```cpp
const int maxn=1e5+5;
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]; 
} 
```
## 最后附上例题
- [P3378 【模板】堆](https://www.luogu.com.cn/problem/P3378)
- [P1886 滑动窗口 /【模板】单调队列](https://www.luogu.com.cn/problem/P1886)
- [P3528 [POI 2011] PAT-Sticks](https://www.luogu.com.cn/problem/P3528)
- [P3372 【模板】线段树 1](https://www.luogu.com.cn/problem/P3372)
- [P3373 【模板】线段树 2](https://www.luogu.com.cn/problem/P3373)
- [P4113 [HEOI2012] 采花](https://www.luogu.com.cn/problem/P4113)
- [P9753 [CSP-S 2023] 消消乐](https://www.luogu.com.cn/problem/P9753)
- [P3367 【模板】并查集](https://www.luogu.com.cn/problem/P3367)
- [bzoj#P2054. 疯狂的馒头](https://hydro.ac/p/bzoj-P2054)
- [P8306 【模板】字典树](https://www.luogu.com.cn/problem/P8306)
- [P10471 最大异或对 The XOR Largest Pair](https://www.luogu.com.cn/problem/P10471)