Tunnel Warfare(树状数组+二分)
程序员文章站
2022-03-12 09:18:09
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 vi...
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);
//freopen("in.txt", "r", stdin);
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;
}
本文地址:https://blog.csdn.net/qq_43543086/article/details/107120762
推荐阅读
-
Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose
-
2020秦皇岛CCPC 7-2 Bounding Wall(树状数组+二分,并查集)
-
BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)
-
Tunnel Warfare(树状数组+二分)
-
【数字_ID】HDU6274 Master of Sequence(二分+树状数组+预处理)
-
D. Multiset(权值线段树/树状数组/二分)
-
Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose
-
BZOJ1901: Zju2112 Dynamic Rankings(整体二分 树状数组)
-
2020秦皇岛CCPC 7-2 Bounding Wall(树状数组+二分,并查集)
-
Tunnel Warfare(树状数组+二分)