25五一集训Day1笔记

# 数据结构  
啊是的，钟神又来给我们讲数据结构了！！
## $queue$
$ queue $是一个古老的东西，古老到……（我也不知道）
总之，$queue$并不难。  
$queue$原名队列，隶属于$queue$库，主要功能有以下几种：
```cpp
q.push(233);
q.push(2233);//向队列里面加入一个元素
q.pop();//从队列中删除一个元素 删除是队列头的元素 233void类型没有返回值
int x = q.front();//获取队列头元素 2233
cout << q.size() << endl;
```
## $stack$
那么，一个竖起来封底的队列，叫啥呢？
————$stack$  。
$stack$，又名栈，也是一种很古老的数据结构，主要支持以下几种操作：
```cpp
q.push(233);
q.push(2233);//向栈里面加入一个元素
q.pop();//从栈中删除一个元素 删除是队列头的元素 2233 void类型没有返回值
int x = q.top();//获取栈顶部元素 233
cout << q.size() << endl;//获取栈剩余的元素个数
```
## $deque$
$deque$，又名单调队列，顾名思义，就是具有单调增减性的队列（$queue$）但是，STL非常贴心的替我们实现完了。
具体如下：
```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";
	} 
		
}
```
## 大小根堆
堆，是一个很神奇的东西，它叫堆，但是它基于队列（没想到吧，又是$queue$），大根堆，就是根节点是整棵树最大的节点，并且每个点的儿子都一定比自己小。小根堆则反之。
直接上示例代码：
```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 
}
```
## 并查集
人见人爱的并查集$baby$来了！  
简单来说就是一堆连通块一点一点连在一起了，优化有路径压缩和“随机合并”。
具体不想多说，详情可见[并查集](https://www.luogu.com.cn/article/z0fvhocv)。
## 上午结束！！！
***
***
## $Trie$
$Trie$,长得像$Tree$，事实上，它也确实是$Tree$，只不过是字典$Tree$。  
这个东西，他比较复杂，比较难讲，总之，由于作者~~太懒太蒟蒻~~不方便，不多赘述。
```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;
}
```
## 分块
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
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;
}
```
### 分治
分治，顾名思义，分开做（以前讲过）。
```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--;
	}
}

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/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