CF1066CBooks Queries（数组的特殊处理）

题意描述

您需要维护一个数据结构，支持以下三种操作：

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

输入输出格式：

输入格式：

第一行，一个整数q,表示操作数

下面q行，每行2个数，表示一个操作

输出格式

对于每个“？”操作，输出一行一个整数，表示答案

思路：

~~差点暴力上treap~~

水题一道

因为只有100000个数，所以我们可以维护一个大小为200000的数组以及lll，rrr两个指针

第一个数放在100000这个位置，每次往左放就l--，反之r++

把数填进去，同时写一个映射，将ididid映射为位置

当前位置−l-l−l为左面的数的数量，r−r-r−当前位置为右面的数的数量

然后输出即可

代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rii register int i

#define rij register int j

using namespace std;

int l,r,now,ys[];

int q;

int main()

{

    scanf("%d\n",&q);

    for(rii=;i<=q;i++)

    {

        char cz;

        int id;

        scanf("%c%d\n",&cz,&id);

        if(i==)

        {

            ys[id]=;

            l=;

            r=;

            continue;

        }

        if(cz=='L')

        {

            l--;

            ys[id]=l;

        }

        if(cz=='R')

        {

            r++;

            ys[id]=r;

        }

        if(cz=='?')

        {

            printf("%d\n",min(ys[id]-l,r-ys[id]));

        }

    }

}

巴特西