hdu 1540&&poj 1892

题目大意：有排成一行的村庄，开始时彼此相连。现在又三种操作：

（1）：D x 破坏x村庄

（2）：R 修复上一次被破坏的村庄

（3）：Q x是求包含村庄x的最长相连村庄数。

比较坑爹的是poj和hdu的R操作有所不同。比如执行了下列操作：

D 2

D 4

D 2

在poj修复的是村庄4，而hdu修复的是村庄2.这是需要注意的。

下面是在poj过的代码。

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 #define lson l,m,rt<<1
  4 #define rson m+1,r,rt<<1|1
  5 #define maxn 50005
  6 struct node
  7 {
  8     int llen,rlen,maxlen;
  9 }setree[maxn<<2];
 10 bool vis[maxn];
 11 int stack[maxn],top;
 12 void build(int l,int r,int rt)
 13 {
 14     setree[rt].maxlen=setree[rt].llen=setree[rt].rlen=r-l+1;
 15     if(l==r)
 16     return;
 17     int m=(l+r)>>1;
 18     build(lson);
 19     build(rson);
 20 }
 21 void pushup(int rt,int len,int m)
 22 {
 23     setree[rt].llen=setree[rt<<1].llen;
 24     if(setree[rt<<1].llen==len-len/2)
 25     setree[rt].llen+=setree[rt<<1|1].llen;
 26     
 27     setree[rt].rlen=setree[rt<<1|1].rlen;
 28     if(setree[rt<<1|1].rlen==len/2)
 29     setree[rt].rlen+=setree[rt<<1].rlen;
 30     
 31     if(setree[rt<<1].maxlen>setree[rt<<1|1].maxlen)
 32         setree[rt].maxlen=setree[rt<<1].maxlen;
 33     else
 34         setree[rt].maxlen=setree[rt<<1|1].maxlen;
 35     if(setree[rt].maxlen<setree[rt<<1].rlen+setree[rt<<1|1].llen){
 36         setree[rt].maxlen=setree[rt<<1].rlen+setree[rt<<1|1].llen;
 37     }
 38 }
 39 void update(int l,int r,int rt,int num,int c)
 40 {
 41     if(l==r){
 42         setree[rt].maxlen=setree[rt].llen=setree[rt].rlen=c;
 43         return;
 44     }
 45     int m=(l+r)>>1;
 46     if(num<=m)
 47     update(lson,num,c);
 48     else
 49     update(rson,num,c);
 50     pushup(rt,r-l+1,m);
 51 }
 52 int query(int l,int r,int rt,int num)
 53 {
 54     if(l==r||setree[rt].maxlen==r-l+1||setree[rt].maxlen==0)
 55     return setree[rt].maxlen;
 56     int m=(l+r)>>1;
 57     if(num<=m){
 58         if(num>=m-setree[rt<<1].rlen+1)
 59             return query(lson,num)+setree[rt<<1|1].llen;
 60         else
 61            return query(lson,num);
 62     }
 63     else{
 64         if(num<=m+setree[rt<<1|1].llen)
 65            return query(rson,num)+setree[rt<<1].rlen;
 66            else
 67           return query(rson,num);
 68     }
 69 }
 70 int main()
 71 {
 72     int n,m;
 73     while(~scanf("%d%d",&n,&m)){
 74     build(1,n,1);
 75     top=-1;
 76     memset(vis,true,sizeof(vis));
 77     while(m--){
 78         char op[5];
 79         scanf("%s",op);
 80         if(op[0]=='D'){
 81             int a;
 82             scanf("%d",&a);
 83             if(!vis[a])
 84             continue;
 85             vis[a]=false;
 86             stack[++top]=a;
 87             update(1,n,1,a,0);
 88         }
 89         else if(op[0]=='R'){
 90             vis[stack[top]]=true;
 91             update(1,n,1,stack[top],1);
 92             top--;
 93         }
 94         else{
 95             int a;
 96             scanf("%d",&a);
 97             if(!vis[a]){
 98                 printf("0\n");
 99                 continue;
100             }
101             printf("%d\n",query(1,n,1,a));
102         }
103     }
104     }
105     return 0;
106 }