const int N =5e4+5;
int t;int n, m;int tree[N];
void add(int k, int num)
{
for (int i = k;i <= n; i += i & -i)
tree[i] += num;
}
int read(int k)
{
int sum = 0;
for (int i = k;i > 0; i -= i & -i)
sum += tree[i];
return sum;
}
bool vis[N];
int main()
{
ios::sync_with_stdio(false);cin.tie(0);
while (cin >> n >> m)
{
memset(tree, 0, sizeof tree);
f(i, 1, n)add(i, 1);
string op;int x;
stack<int> st;
memset(vis, false, sizeof vis);
while (m--)
{
cin >> op;
if (op == "D")
{
cin >> x;
if (!vis[x])
{
add(x, -1);
st.push(x);
vis[x] = true;
}
}
else if (op == "R")
{
if (st.empty())continue;
int now = st.top();st.pop();
if (vis[now])
{
vis[now] = false;
add(now, 1);
}
}
else
{
cin >> x;
if (vis[x])printf("0\n");
else
{
int le, re;
int l = 1, r = x;
while (l <= r)
{
int mid = l + r >> 1;
if (read(x) - read(mid-1) == x - mid+1) { le = mid;r = mid - 1; }
else l = mid + 1;
}
l = x, r = n;
while (l <= r)
{
int mid = l + r >> 1;
if (read(mid) - read(x - 1) == mid - x + 1) { re = mid;l = mid + 1; }
else r = mid - 1;
}
printf("%d\n", re - le + 1);
}
}
}
}
return 0;
}
Processed:
0.012, SQL:
9
