[hdoj1540]Tunnel Warfare

Tunnel Warfare

题意

在一条线上有二种操作

• 删掉一个点
• 恢复一个点

求某一个点和与之相连点的个数。

题解

线段树设左右标志或者是树状数组二分

HDOJ可以线段树+二分。

---

Cnm hdoj 多组数据不给提示

如果是树状数组500ms，线段树+二分1500ms。

POJ卡了线段树+二分。HDOJ没有写多组输入害得我WA成sb了。

垃圾HDOJ还造假数据，毁坏多个碉堡。也是服了。

WA代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4+10;
int sum[maxn<<3],vis[maxn],last[maxn];
int n,q;
void pushup(int rt){
    sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt){
    if(l==r){
        sum[rt] = 1;
        return;
    }
    int mid = l+r>>1;
    build(lson); build(rson);
    pushup(rt);
}
void update(int val,int p,int l,int r,int rt){
    if(l==r && l==p){
        sum[rt] = val;
        return;
    }
    int mid = l+r>>1;
    if(p <= mid) update(val,p,lson);
    if(mid < p) update(val,p,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l && r<=R){
        return sum[rt];
    }
    int mid = l+r>>1;
    int ans = 0;
    if(L <= mid) ans += query(L,R,lson);
    if(mid < R) ans += query(L,R,rson);
    return ans;
}
bool check(int l,int r){
    if(query(l,r,1,n,1) == r-l+1) return true;
    return false;
}
int solve1(int l,int r,int rt){
    int mid;int st = n;
    while(l<=r){
        mid = l+r>>1;
        if(check(mid,r)) r = mid-1,st = mid;
        else l = mid+1;
    }
    return st;
}
int solve2(int l,int r,int rt){
    int mid ;int ed = n;
    while(l<=r){
        mid = l+r>>1;
        if(check(l,mid)) l = mid+1,ed = mid;
        else r = mid-1;
    }
    return ed;
    //cout<<ed<<' ';
}
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&q)){
    build(1,n,1);
    rep(i,1,n+1) vis[i] = 1;
    int top = 0;
    while(q--){
        char op[20];
        scanf("%s",op);
        if(op[0] == 'D'){
            int x; scanf("%d",&x);
            update(0,x,1,n,1);
            last[top++] = x;
        }else if(op[0] == 'R'){
            int x =last[--top];
            update(1,x,1,n,1);
        }else{
            int x;scanf("%d",&x);
            if(query(x,x,1,n,1)==0){
                puts("0");
                continue;
            }
            printf("%d\n",solve2(x,n,x)-solve1(1,x,x)+1);
        }
    }
    }

    return 0;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
int n,m;
const int maxn = 5e4+20;
int bit[maxn];
int lowbit(int x){
    return x&-x;
}
int query(int x){
    int ans = 0;
    for(int i = x;i;i-=lowbit(i)){
        ans += bit[i];
    }
    return ans;
}
int query(int l,int r){
    return query(r)-query(l-1);
}
void add(int x,int val){
    for(int i=x;i<=n;i+=lowbit(i)){
        bit[i] += val;
    }
}
int solve_left(int l,int r){
    int mid = l+r>>1;int ans = r;
    while(l<=r){
        mid = l+r>>1;
        if(query(mid,r)==r-mid+1) r = mid-1,ans = mid;
        else l = mid+1;
    }
    return ans;
}
int solve_right(int l,int r){
    int mid,ans = l;
    while(l<=r){
        mid = l+r>>1;
        if(query(l,mid)==mid-l+1) l=mid+1,ans = mid;
        else r = mid-1;
    }
    return ans;
}
int vis[maxn];
int main(){
#ifdef LOCAL
    freopen("2.in","r",stdin);
#endif
    while(scanf("%d%d",&n,&m)!=EOF){
        stack<int> st;
        memset(bit,0,sizeof(bit));
        memset(vis,0,sizeof(vis));
        rep(i,1,n+1) add(i,1);
        while(m--){
            char op[20];scanf("%s",op);
            if(op[0]=='D'){
                int x;scanf("%d",&x);
                st.push(x);
                if(vis[x]) continue;
                vis[x] = 1;
                add(x,-1);
            }else if(op[0]=='Q'){
                int x;scanf("%d",&x);
                if(query(x,x)==0) puts("0");
                else printf("%d\n",solve_right(x,n)-solve_left(1,x)+1);
            }else{
                add(st.top(),1);
                vis[st.top()] = 0;
                st.pop();
            }
        }
    }

    return 0;
}