CF1066C题解

ncwzdlsd · 2023-01-23 17:30:10 · 题解

题目要求我们维护一种数据结构，支持以下三种操作：

• L id：在现在序列的左边插一个编号为 id 的物品
• R id：在现在序列的右边插一个编号为 id 的物品
• ? id：查询该点左面有几个元素，右面有几个元素，并取 \min 输出

看到这道题，很容易想到可以用 STL 中的双端队列来解决问题，不过这个东西占用空间极大，于是乎我们明智地采用数组来模拟双端队列的操作。

用数组模拟 STL 容器的应用有很多，比如数组模拟栈、数组模拟队列等，感兴趣的可以自己尝试。

对于此题要求的 3 种操作，代码实现如下：

for(int i=1;i<=T;i++)
{
    char ch;int x;
    cin>>ch>>x;
    if (ch=='L') a[x]=--l;
    if (ch=='R') a[x]=++r;
    if (ch=='?') printf("%d\n",min(a[x]-l,r-a[x]));
}