抄袭党请跳到最后
题目描述
给定一个双端队列,初始时队列为空。
你要对其进行 q 次操作,每次操作可能是以下三种之一:
L x,从队列的左端插入整数 x。
R x,从队列的右端插入整数 x。
? x,请你计算为了使已经处于队列中的整数 x 位于队列的最左端或最右端,至少需要从最左端或最右端弹出多少个数字。
保证操作 3 一定合法( ? x 中的 x 一定已经处于队列之中)。
每个数字最多被插入到队列中 1 次(队列中一定不会存在重复数字)。
注意,操作 3 只是询问最少需要弹出多少数字,不是真的要弹出它们,队列中的数字始终不会减少。
输入格式
第一行包含整数 q。
接下来 q 行,每行包含一个操作信息,格式如题所述。
输出格式
对于每个操作 3,输出一行,一个整数表示结果。
数据范围
对于 30% 的数据,$1≤q≤30$,$1≤x≤30$。
对于 100% 的数据,$1≤q≤2×10^5$,$1≤x≤2×10^5$。
保证至少包含一个操作 3,
保证操作 1 和 2 不会重复插入数字。
保证操作 3 不会询问队列中不存在的数字。
输入样例1
8
L 1
R 2
R 3
? 2
L 4
? 1
L 5
? 1
输出样例1
1
1
2
输入样例2
10
L 100
R 100000
R 123
L 101
? 123
L 10
R 115
? 100
R 110
? 115
输出样例2
0
2
1
算法1
(模拟) $O(t)$
注意数据范围:对于 100% 的数据,$1≤q≤2×10^5$,$1≤x≤2×10^5$。
所以我们不需要真的去开一个双端队列,开一个长度是$4e5+10$的数组就可以了,用head,tail去当队头和队尾。
因为保证操作 1 和 2 不会重复插入数字。
所以可以用unordered_map[HTML_REMOVED]去离散化一下,把数字对应到下标上。
然后就可以快乐的写代码了!!!
时间复杂度
$O(t)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int a[N];
char op[2];
int head=2e5,tail=2e5,x;
unordered_map<int,int> m;
int main(){
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%d",op,&x);
if(op[0]=='L')
{
while(a[head]!=0) head--;
a[head]=x;
m[x]=head;
}
else if(op[0]=='R')
{
while(a[tail]!=0) tail++;
a[tail]=x;
m[x]=tail;
}
else printf("%d\n",min(m[x]-head,tail-m[x]));
}
return 0;
}