五一

# 小胖时隔一年再次震惊全场
## 程序：算法 数据结构
### 队列：
FIFO：first in first out，先进先出  
手写或stl：queue  
push：进队  
front：队首  
pop：出队（把队首踢出去）
size：大小
empty：空  
endl！！！慢速畅
### 小胖太有实力了
### 233！感觉讲的比隔壁j组还简单
```cpp
struct queue{
	int a[1000];
	int head=1,tail=0;
	void push(int x){
		a[++tail]=x;
	}
	void pop(){
		head++;
	}
	int front(){
		return a[head];
	}
	int size(){
		return tail-head+1;
	}
}; 
int main(){
	return 0;
}
```
手写队列
### 栈：
FILO:first in last out,先进后出
## 作用
栈dfs，队列bfs
### 大样例：
阴历：很大的阳历
### 单调队列
删保持单调  
实现：双端、手写
### 双指针
很重要的优化技巧
### 堆

```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
#include<bits/stdc++.h>
using namespace std;
int n,m,f[10005],size[10005];
int find(int x){
    if(x==f[x])return x;
    return f[x]=find(f[x]);
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(size[x]>size[y])swap(x,y);
    f[x]=y;
    size[y]+=size[x];
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=n;i++)size[i]=1;
    while(m--){
        int z;
        cin>>z;
        if(z==1){
            int x,y;
            cin>>x>>y;
            merge(x,y);
        }
        else{
            int x,y;
            cin>>x>>y;
            if(find(x)==find(y))cout<<'Y'<<'\n';
            else cout<<'N'<<'\n';
        }
    }
}
```
### 单调栈没用
### trie

```cpp
#include<bits/stdc++.h>
using namespace std;
int t[3000005][63],tot,cnt[3000005];
char s[3000005];
int gn(char opt){
	if(opt>='a'){
		return opt-'a'+1;
	}
	else if(opt>='A'){
		return opt-'A'+1+26;
	}
	else{
		return opt-'0'+1+52;
	}
}
void insert(char s[]){
	int p=0,len=strlen(s);
	for(int i=0;i<len;i++){
		int c=gn(s[i]);
		if(!t[p][c])t[p][c]=++tot;
		p=t[p][c];
		cnt[p]++;
	}
}
int find(char s[]){
	int p=0,len=strlen(s);
	for(int i=0;i<len;i++){
		int c=gn(s[i]);
		if(!t[p][c])return 0;
		p=t[p][c];
	}
	return cnt[p];
}
signed main(){
	int tt;
	scanf("%d",&tt);
	while(tt--){
		for(int i=1;i<=tot;i++)
		{
			cnt[i]=0;
			for(int j=1;j<=62;j++)
			{
				t[i][j]=0;
			}
		}
		tot=0;
		int n,q;
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%s",s);
			insert(s);
		}
		while(q--){
			scanf("%s",s);
			printf("%d\n",find(s));
		}
	}
}
```
### 分块
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
const int man=100010;
int belong[man];
int siz[man];
int sum[man];
int delta[man];
signed main(){
	int n,m;
	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++)sum[belong[i]]=sum[belong[i]]+a[i],siz[belong[i]]++;
	for(int i=1;i<=m;i++){
		int opt;
		cin>>opt;
		if(opt==1){
			int l,r,v;
			cin>>l>>r>>v;
			if(belong[l]==belong[r]){
				for(int j=l;j<=r;j++){
					a[j]+=v;
					sum[belong[j]]+=v;
				}
			}
			else{
				for(int j=l;belong[j]==belong[l];j++){
					a[j]+=v;
					sum[belong[j]]+=v;
				}
				for(int j=belong[l]+1;j<belong[r];j++){
					delta[j]+=v;
					sum[j]+=siz[j]*v;
				}
				for(int j=r;belong[j]==belong[r];j--){
					a[j]+=v; 
					sum[belong[j]]+=v;
				}
			}
		}
		else{
			int l,r,ans=0;
			cin>>l>>r;
			if(belong[l]==belong[r]){
				for(int j=l;j<=r;j++){
					ans+=a[j]+delta[belong[j]];
				}
			}
			else {
				for(int j=l;belong[j]==belong[l];j++)ans+=a[j]+delta[belong[j]];
				for(int j=belong[l]+1;j<belong[r];j++){
					ans+=sum[j];
				}
				for(int j=r;belong[j]==belong[r];j--)ans+=a[j]+delta[belong[j]];
			}
			cout<<ans<<'\n';
		}
	}
}
```
### 莫队
跳过
### 分治逆序对

```cpp
#include<bits/stdc++.h>
using namespace std;
int a[500005];
long long n,b[500005],cnt;
void sor(int l,int r){
	if(l==r)return;
	int mid=l+r>>1;
	sor(l,mid);
	sor(mid+1,r);
	int lp=l;
	int rp=mid+1;
	int pp=l;
	while(lp<=mid&&rp<=r){
		if(a[lp]<=a[rp])b[pp++]=a[lp++];
		else{b[pp++]=a[rp++];cnt+=mid-lp+1;}
	} 
	while(lp<=mid)b[pp++]=a[lp++];
	while(rp<=r)b[pp++]=a[rp++];
	for(int i=l;i<=r;i++)a[i]=b[i];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sor(1,n);
	cout<<cnt;
}
```