POJ 2892 - Tunnel Warfare

题目描述

Tunnel Warfare

解法：树状数组 - 二分

树状数组是很好理解的，每个位置上的$c[x]$记录的也就是村庄$x$前面没有被摧毁的村庄数。

但是如何计算跟村庄$x$连通的村庄数呢？二分枚举

首先说明$a,b$分别记录的的是最左边与村庄$x$连通的村庄的位置和最右边与村庄$x$连通的村庄位置，这样一来，确定$a,b$之后即可求得连通的村庄数为$b?a+1$

接着我们说如何确定$a,b$？

在$[1,x]$中，我们通过二分法寻找$a$的位置。村庄$x$到中间指针所指村庄是否连续（中间没有被摧毁的村庄）可以通过$sum(x)?sum(m)=x?m$来判断，如果等式不满足则左指针跳到$m+1$的位置，继续搜寻；如果满足，我们让$a$指到$m+1$的位置，右指针指到$m?1$的位置，继续搜索是否$a$的位置可以继续往前移。同理可在$[x,n]$中，寻找$b$的位置。

这里值得注意的是在满足等式后$a$跳转到的位置是$m+1$，因为我们无法断定$m$当前所指的村庄是否被摧毁，而在下一次搜寻中，$m$所指位置的村庄会再次被考查。在$[x,n]$中，$b$跳转到的位置则是$m$，这是因为如果$m$所指村庄是否被摧毁是会直接影响等式是否成立。

#include <iostream>
#include <string.h>
using namespace std;const int N = 50007;
int s[N], c[N];
bool vis[N];
int n, t;inline int lowbit(int x){
    return x&(-x);}void add(int x, int v)
{
    for(int i=x;i<=n;i+=lowbit(i))c[i] += v;
}int sum(int x)
{
    int s = 0;for(int i=x;i>0;i-=lowbit(i))s += c[i];return s;
}int main()
{
    ios::sync_with_stdio(false);while(cin >> n >> t){
    memset(vis, 1, sizeof(vis));memset(c, 0, sizeof(c));int cur = 0;for(int i=1;i<=n;i++)add(i, 1);char opt;int x = 0;while(t--){
    cin >> opt;if(opt!='R') cin >> x;if(opt=='D'){
    s[cur++] = x;if(vis[x]){
    vis[x] = false;add(x, -1);}}else if(opt=='R'){
    if(cur>0){
    x = s[--cur];add(x, 1);vis[x] = true;}}else if(opt=='Q'){
    if(!vis[x]){
    cout << 0 << endl;continue;}int tmp = sum(x), a = 1, b = n;int l = 0, r = x;while(l<=r){
    int m = (l+r)>>1;if(tmp-sum(m)==x-m){
    a = m+1;r = m-1;}else l = m+1;}l = x, r = n;while(l<=r){
    int m = (l+r)>>1;if(sum(m)-tmp==m-x){
    b = m;l = m + 1;}else r = m - 1;}cout << b-a+1 << endl;}}}return 0;
}