题目描述
blablabla
比赛的时候胡了一个树状数组。
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
const int d = 2e5;
int tr[N];
int q, res;
int l = d + 1, r = d + 2;
map<int, int> mp;
int lowbit(int x) {
return x & -x;
}
void add(int x, int d) {
for (int i = x; i < N; i += lowbit(i)) tr[i] += d;
}
int query(int x) {
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i)) sum += tr[i];
return sum;
}
int main() {
char op[2];
int x;
scanf("%d", &q);
while (q --) {
scanf("%s%d", op, &x);
if (*op == 'L') {
mp[x] = l;
add(l, 1);
l --;
res ++;
}
else if (*op == 'R') {
mp[x] = r;
add(r, 1);
r ++;
res ++;
}
else {
int a = query(mp[x]) - 1;
int b = res - a - 1;
cout << min(a, b) << endl;
}
}
return 0;
}
%
正解要短很多 枯了