复习笔记_ 复习单调队列

单调队列dafa is good, it makes $ \mathrm O(n^2) $ becomes $ \mathrm O(n) $

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define MAXN 10086
#define INF 10086
using namespace std;
int n;
int q[MAXN];//单调队列
int bh[MAXN];//记录编号,防止删除时错删:b[i]表示队列中第i位元素的入队时间
int l=0,r=0;//队列首位
int cnt,CNT;//记录编号是第几个入/出队的
int que()
{
return q[l];//根据单调队列性质,队首即为最小值
}
int insert(int x)
{
while(q[r]>=x&&l<=r)//插入元素时队列中比此元素大的其实都没有用了(入队比x早,所以出队比x早,又比x大,在x出队前肯定不会是队首元素)
{
r--;//寻找恰好比x小的元素
}
q[++r]=x;//入队
bh[r]=++cnt;//记录编号,可以看出cnt表示x是第cnt个入队的元素
}
void del()
{
if(bh[l]==++CNT)//CNT表示已经删除了几个元素,显然在队列中第几个入队就应该第几个出队(CNT++其实就表示一个元素已经出队,只不过没有出单调队列)
{
l++;//出单调队列
}//若不满足则说明之前出队的都非队首,对单调队列没有影响
}
int main()
{
// memset(q,0x7fffff,sizeof(q));
// q[0]=0;
q[l]=INF;//如不初始化可能出错
cin>>n;
int x;
int y;
for(int i=1;i<=n;i++)
{
cin>>x;
if(x==1)
{
cin>>y;
insert(y);
}
if(x==2)
{
if(l<=r)
cout<<que()<<endl;
else
cout<<"none"<<endl;
}
if(x==3)
{
del();
}
}
return 0;
}

by宽嫂
qwq