2025.5.1 集训 Day1

# 集训Day1
## 数据结构
### 暴力
不用说了，最简单的写法，也是最笨的，TLE 几率 80%。尽量别用，用点其他的算法。
### queue | 队列
简单，先进先出，具体操作见 [OI-Wiki](https://oi-wiki.org/ds/queue/)。
### stack | 栈
简单，先进后出，具体操作见 [OI-Wiki](https://oi-wiki.org/ds/stack/)。
### 并查集
开始，每个元素假设有一个箭头，每次操作把操作对象的箭头指向指定对象，这样操作完，一直顺着箭头跑，最终指向同一个对象的就是同一个并集。（最后一个指向自己）

放一张图：

![](https://cdn.luogu.com.cn/upload/image_hosting/1erkhh0g.png)

### deque | 双端队列
deque，双端队列，用法如下：
```cpp
push_front(n); //往队头插入元素 n
push_back(n); //往队尾插入元素 n
pop_front(); //删除队头元素
pop_back(); //删除队尾元素
front(); //返回队头元素
back(); //返回队尾元素
```
这里由于队头队尾效果一样，所以怎么用都行

~~但由于同时包括了 stack 和 queue 的功能，所以时间和内存都占用的多，所以非特殊情况尽量不要使用~~。
### priority_queue | 优先队列
结构有点像二叉树。

优先队列，顾名思义，自动排序。定义和操作：
```cpp
定义：
priority_queue<int> g; //默认大根堆
priority_queue<int,vector<int>,greater<int> > g; //greater 小根堆
priority_queue<int,vector<int>,less<int> > g; //less 大根堆

操作：
push(n); //插入元素 n，n变为叶子节点，自动排序
pop(); //删除根节点，根节点的左儿子顶上，自动排序
top(); //返回根节点

排序机制：
大根堆：如果父亲节点小于任意儿子，则与那个儿子交换值。
两个儿子都满足就跟大的换，一样大就跟左儿子换。

小根堆：如果父亲节点大于任意儿子，则与那个儿子交换值。
两个儿子都满足就跟小的换，一样大就跟左儿子换。
```
### Two pointer | 双指针
双指针是一种简单而又灵活的技巧和思想，单独使用可以轻松解决一些特定问题，和其他算法结合也能发挥多样的用处。

双指针顾名思义，就是同时使用两个指针，在序列、链表结构上指向的是位置，在树、图结构中指向的是节点，通过或同向移动，或相向移动来维护、统计信息。

如果不和其他数据结构结合使用，双指针维护区间信息的最简单模式就是维护具有一定单调性，新增和删去一个元素都很方便处理的信息，就比如正数的和、正整数的积等等。

示例代码：
```cpp
signed 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]
	}
    return 0;
}
```