5.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 
} 
```
队列：一种数据结构，实现从后面进，前面出
|函数|作用|
|:-:|:-:|
|q.push()|向队列里面加入一个元素|
|q.pop()|从队列中删除一个元素 删除是队列最前面的元素 
|q.front()|获取队列顶部元素|
|q.size()|获取队列剩余的元素个数|

手写队列：

```
#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<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 
} 
```
例题：告诉你两个数 $n,m$ 和一个长度为 $n$ 的数列 要求从 $a_1,a_2,a_3……a_m$、$a_2,a_3,a_4……a_{m+1}$ 开始求出每个序列的最小值，$1\le n,m\le10^7$   
用普通队列肯定做不了，可以用双端队列deque
|函数|作用|
|:-:|:-:|
|q.push_front()|从双端队列前面加入一个元素|
|q.pop_front()|从双端队列前面删除一个元素 |
|q.front()|获取队列前面元素|
|q.push_back()|从双端队列后面加入一个元素|  
|q.pop_back()|从双端队列前面删除一个元素  
|q.back()|获取队列后面元素|
|q.size()|获取队列剩余的元素个数|

```cpp
//告诉你两个数 $n,m$ 和一个长度为 $n$ 的数列 要求从 $a_1,a_2,a_3……a_m$、$a_2,a_3,a_4……a_{m+1}$ 开始求出每个序列的最小值，$1\len,m\le10^7$ 
#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";
	} 
		
}
```
堆：一种特殊的完全二叉树  
小根堆：父节点值 $\le$ 子节点值，根节点最小  
大根堆：子节点值 $\le$ 父节点值，根节点最大  
|函数|作用|
|:-:|:-:|
|q.push()|向堆里面加入一个元素|
|q.pop()|从堆中删除一个元素 删除是堆最大或最小的元素 
|q.top()|获取堆顶部元素|
|q.size()|获取堆剩余的元素个数|

堆不仅能存变量，还能存结构体  
如果要把结构体 放入 stl比大小 只能重载小于号

```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;
	} 
};
```
并查集：将两个集合合并成一个  
判断两个集合是否属于同一个并查集只用判断最后它们所有点走到的最终的点是不是一致的  
正解：

```cpp
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;
	
	//合并
	to[go(p1)] = go(p2);
	
	//查询
	go(p1) == go(p2); 
}
```

```cpp
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;
	
	//合并
	to[go(p1)] = go(p2);
	
	//查询
	go(p1) == go(p2); 
}
```
非正解之随机合并：

```cpp
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;
	
	//合并
	if (rand()%2)
		to[go(p1)] = go(p2);
	else
		to[go(p2)] = go(p1);
	
	//查询
	go(p1) == go(p2); 
}
```
解决问题：有 $n$ 个数,$m$ 个操作,每个操作都有三个数 $l,r,x$，表示把从 $l$ 到 $r$ 的数全部赋值为 $x$，$1\le n,m \le10^7$.   
这道题因为数据太大不能用线段树，要记住  **正难则反**  
我们可以倒着遍历，每次都可以直接覆盖，并且把第 $l$ 个直接并查连到第 $r+1$个，这样就不会重复覆盖了

```cpp
//解决问题：有 $n$ 个数,$m$ 个操作,每个操作都有三个数 $l,r,x$，表示把从 $l$ 到 $r$ 的数全部赋值为 $x$，$1\le n,m \le10^7$. 
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;
		} 
	} 
}
```
小知识：双指针

```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]
	}
}
```
论证:为什么写代码要用"\n"而不是endl?

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

using namespace std;

int main()
{
	freopen("1.txt","w",stdout);//重定向到文件输出  
	
	for (int i=1;i<=10000000;i++)
		//cout << i << endl;//14.08s
		cout << i << "\n";//0.9579s
	
	return 0;
}
```
**警示：如果你TLE，很有可能是因为写了endl,写代码要用"\n"而不是endl**  
分块：https://oi-wiki.org/ds/decompose/  
线段树的模板题也可以用它做

```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;
}
```
trie:  https://oi-wiki.org/string/trie/  
[例题](https://www.luogu.com.cn/problem/P10471)

```cpp
struct node
{
	int nxt[2];//nxt[0] nxt[1] 代表从当前点走0和1会走到哪里 走到0的话代表这个节点不存在 
	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;//取出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;
}
```
莫队： https://oi-wiki.org/misc/mo-algo/  
[例题](https://www.luogu.com.cn/problem/P4113)

```cpp
struct query
{
	int l,r,id,ans;
}q[maxn];

bool cmp1(const query &q1, const query &q2)
{
	if (belong[q1.l] != belong[q2.l]) return belong[q1.l] < belong[q2.l];
	else return q1.r < q2.r;
}

bool cmp2(const query &q1, const query &q2)
{
	return q1.id < q2.id;
}

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

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

int main()
{
	cin >> n >> m;
	for (int i=1;i<=n;i++)
		cin >> a[i];
	for (int i=1;i<=m;i++)
	{
		cin >> q[i].l >> q[i].r;
		q[i].id = i;
	}
	int s = sqrt(n);
	for (int i=1;i<=n;i++)
		belong[i] = i/s+1;
	sort(q+1,q+m+1,cmp1);	
		
	for (int i=q[1].l;i<=q[1].r;i++)
		ins(a[i]);
	q[1].ans = ans;
	for (int i=2;i<=m;i++)//O(Nsqrt(N))
	{
		int l1=q[i-1].l,r1=q[i-1].r;
		int l2=q[i].l,r2=q[i].r;
		
		if (l1 < l2)
			for (int i=l1;i<l2;i++)
				del(a[i]);
		else
			for (int i=l2;i<l1;i++)
				ins(a[i]);
		
		if (r1 < r2)
			for (int i=r1+1;i<=r2;i++)
				ins(a[i]);
		else
			for (int i=r2+1;i<=r1;i++)
				del(a[i]);

q[i].ans = ans;
	}
	sort(q+1,q+m+1,cmp2);
	for (int i=1;i<=m;i++)
		cout << q[i].ans << "\n";
		
	return 0;
}
```
最后再来个简单的[逆序对](https://www.luogu.com.cn/problem/P1908)

```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]; 
} 
```
**题单**  
https://www.luogu.com.cn/problem/P3378  
https://www.luogu.com.cn/problem/P1886  
https://www.luogu.com.cn/problem/P3528  
https://www.luogu.com.cn/problem/P3372  
https://www.luogu.com.cn/problem/P3373  
https://www.luogu.com.cn/problem/P4113  
https://www.luogu.com.cn/problem/P9753  
https://www.luogu.com.cn/problem/P3367  
https://hydro.ac/p/bzoj-P2054   
https://www.luogu.com.cn/problem/P8306  
https://www.luogu.com.cn/problem/P10471