[hdoj1540]Tunnel Warfare

Tunnel Warfare

题意

在一条线上有二种操作

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

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

题解

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

HDOJ可以线段树+二分。


Cnm hdoj 多组数据不给提示

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

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

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

WA代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#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;
}