http://poj.org/problem?id=2892
记录每个区间端点的左连续及右连续 都是单点更新 用不着向下更新 还简单点
找错找了N久 最后发现将s[w<<1|1]写成s[w<<1+1]了
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 #define N 50010 7 int lr[N<<2],rr[N<<2],stack[N<<2]; 8 void build(int l,int r,int w) 9 { 10 lr[w] = rr[w] = r-l+1; 11 if(l==r) 12 return ; 13 int m = (l+r)>>1; 14 build(l,m,w<<1); 15 build(m+1,r,w<<1|1); 16 } 17 void pushup(int l,int r,int w) 18 { 19 int m = (l+r)>>1; 20 lr[w] = lr[w<<1]; 21 rr[w] = rr[w<<1|1]; 22 if(lr[w<<1]==m-l+1) 23 lr[w] += lr[w<<1|1]; 24 if(rr[w<<1|1]==r-m) 25 rr[w]+=rr[w<<1]; 26 } 27 void update(int p,int d,int l,int r,int w) 28 { 29 if(l==r) 30 { 31 lr[w] = d; 32 rr[w] = d; 33 return ; 34 } 35 int m = (l+r)>>1; 36 if(p<=m) 37 update(p,d,l,m,w<<1); 38 else 39 update(p,d,m+1,r,w<<1|1); 40 pushup(l,r,w); 41 } 42 int query(int p,int l,int r,int w) 43 { 44 if(lr[w]==r-l+1) 45 return lr[w]; 46 if(l==r) 47 return 0; 48 int m = (l+r)>>1; 49 if(p<=m) 50 { 51 if(m-rr[w<<1]<p) 52 return rr[w<<1]+lr[w<<1|1]; 53 return query(p,l,m,w<<1); 54 } 55 else 56 { 57 if(m+lr[w<<1|1]>=p) 58 return lr[w<<1|1]+rr[w<<1]; 59 return query(p,m+1,r,w<<1|1); 60 } 61 } 62 int main() 63 { 64 int n,m,k,g=0; 65 char ss[5]; 66 while(cin>>n>>m) 67 { 68 build(1,n,1); 69 g=0; 70 while(m--) 71 { 72 scanf("%s",ss); 73 if(ss[0]=='D') 74 { 75 scanf("%d",&k); 76 stack[++g] = k; 77 update(k,0,1,n,1); 78 } 79 else if(ss[0]=='Q') 80 { 81 scanf("%d",&k); 82 printf("%d ",query(k,1,n,1)); 83 } 84 else 85 { 86 update(stack[g],1,1,n,1); 87 g--; 88 } 89 } 90 } 91 return 0; 92 }