就是维护两个端点下标,和当前数的插入时的下标。
第一个数 0
左边插的数 -1 -2 ....
右边插得数 1 2 …
左右端点下标错开l = 0, r = -1
因为用的--l 和++r
,
所以第一个点如果是L 下标就是-1,这时他左边的点下标 -2,-3,-4…
右边点下标 0, 1, 2…
如果第一个点是R,下标++r = 0, 他右边的点下标1, 2, 3…
左边点下标 -1, -2, -3…
。。。。
-4-3-2-1
先插L
p[x] - l = -1 - (-4) = 3 第一个点左边3个数
r - p[x] = -1 - (-1) = 0 第一个点右边0个数
先插R同理
这样减起来数量就对了。p[x] - l
就是左边点的个数
r - p[x]
就是右边点的个数
题意所需即左边来看,就是它的下标减去左边的下标 = 它到左端的数的数量。
右端同理。取min即可。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 200010;
int m;
int p[N]; //存数对应的队里的下标
int main()
{
cin >> m;
int l = 0, r = -1; //最左边下标0,最右边下标 -1
while (m -- )
{
char c;
int x;
cin >> c >> x;
if (c == 'L') p[x] = -- l;
else if (c == 'R') p[x] = ++ r;
else if (c == '?') printf("%d\n", min(r - p[x], p[x] - l));
}
return 0;
}
平行世界里假如我们取l = 0, r = 1
那么,插入就要改成
p[x] = l--, p[x] = r++
第一个点L 下标 0,左边点:-1, -2, -3…
右边点 1, 2, 3…
第一个点R 下标 1,左边点: 0, -1, -2…
右边点: 2, 3, 4,…
。。。。
-3-2-10
p(x) - l = 0 - (-3) = 3 左边三个
r - p(x) = 1 - 0 = 1 右边一个 多了一,所以减去
先插R同理
如果先插R p[x] - l
多了一,如果先插Lr - p[x]
多了一,所以取min后减一(由于他俩都是数量,即正数,所以可以把减一提出来)
const int N = 200010;
int m;
int p[N]; //存数对应的队里的下标
int main()
{
cin >> m;
int l = 0, r = 1; //最左边下标0,最右边下标 -1
while (m -- )
{
char c;
int x;
cin >> c >> x;
if (c == 'L') p[x] = l--;
else if (c == 'R') p[x] = r++;
else if (c == '?') printf("%d\n", min(r - p[x], p[x] - l)-1);
}
return 0;
}