Hdu 1540_牛客博客

【题意】给定两个整数N，M, 其中N表示一共有N个村庄，M代表有M次操作，操作有以下：

1.D x 销毁村庄x

2.Q x 询问与村庄x相邻的村庄总数

3.R 最近一次销毁的村庄得到重建

【解题思路】一看这个修改和查询就想到了线段树，然后这个题和以前做过的poj 的 Hotel很像都是区间合并，那个题由于是区间修改还比这个题难一点，这一次完全靠自己裸这个区间和并，开始想得很清楚，就在线段树的节点里面维护三个变量，ls,rs,ms，分别表示区间的左连续长度，区间的右连续长度，以及整个区间的连续长。这个题目难点肯定是区间合并了，那么具体怎么合并，请看我的Push_Up（）

void Push_Up(int rt)
{
    Tree[rt].ls = Tree[rt<<1].ls;
    Tree[rt].rs = Tree[rt<<1|1].rs;
    Tree[rt].ms = max(Tree[rt<<1].rs+Tree[rt<<1|1].ls,max(Tree[rt<<1].ms,Tree[rt<<1|1].ms));
    if(Tree[rt<<1].ls==Tree[rt<<1].r-Tree[rt<<1].l+1)//left son tree echo.
    {
        Tree[rt].ls += Tree[rt<<1|1].ls;
    }
    if(Tree[rt<<1|1].rs==Tree[rt<<1|1].r-Tree[rt<<1|1].l+1)
    {
        Tree[rt].rs += Tree[rt<<1].rs;
    }
}

【AC代码】

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int nn = 50010;
struct node{
    int l,r;
    int ls,rs,ms;
}Tree[nn<<2];
void Build(int l,int r,int rt)
{
    Tree[rt].l = l;
    Tree[rt].r = r;
    Tree[rt].ls = Tree[rt].rs = Tree[rt].ms = r-l+1;
    if(l==r) return ;
    int m = (l + r)>>1;
    Build(lson);
    Build(rson);
}
void Push_Up(int rt)
{
    Tree[rt].ls = Tree[rt<<1].ls;
    Tree[rt].rs = Tree[rt<<1|1].rs;
    Tree[rt].ms = max(Tree[rt<<1].rs+Tree[rt<<1|1].ls,max(Tree[rt<<1].ms,Tree[rt<<1|1].ms));
    if(Tree[rt<<1].ls==Tree[rt<<1].r-Tree[rt<<1].l+1)//left son tree echo.
    {
        Tree[rt].ls += Tree[rt<<1|1].ls;
    }
    if(Tree[rt<<1|1].rs==Tree[rt<<1|1].r-Tree[rt<<1|1].l+1)
    {
        Tree[rt].rs += Tree[rt<<1].rs;
    }
}
void Update(int pos,int val,int rt)
{
    if(Tree[rt].l==Tree[rt].r)
    {
        Tree[rt].ls = Tree[rt].rs = Tree[rt].ms = val;
        return ;
    }
    int m = (Tree[rt].l+Tree[rt].r)>>1;
    if(pos<=m)
    {
        Update(pos,val,rt<<1);
    }
    else
    {
        Update(pos,val,rt<<1|1);
    }
    Push_Up(rt);
}
int query_ans(int x,int rt)
{
    if(Tree[rt].l==Tree[rt].r||Tree[rt].ms==0||Tree[rt].ms==Tree[rt].r-Tree[rt].l+1)
        return Tree[rt].ms;
    int m = (Tree[rt].l+Tree[rt].r)>>1;
    if(x<=m)
    {
        //x在左子树的右区间，要考虑右子树的左区间
        if(x>=Tree[rt<<1].r-Tree[rt<<1].rs+1)
        {
            return query_ans(x,rt<<1)+query_ans(m+1,rt<<1|1);//特别注意这里的m+1，不能取m
        }
        else
            return query_ans(x,rt<<1);
    }
    else
    {
        //x在右子树的左区间，要考虑左子树的右区间
        if(x<=Tree[rt<<1|1].l+Tree[rt<<1|1].ls-1)
        {
            return query_ans(x,rt<<1|1)+query_ans(m,rt<<1);//特别注意这里的m，要取等号
        }
        else
            return query_ans(x,rt<<1|1);
    }
}

int main()
{
   int n,m;
//   ios::sync_with_stdio();cin.tie(0);
   int q[nn],cnt=0;
   while(~scanf("%d%d",&n,&m))
   {
       Build(1,n,1);
       cnt = 0;
       char command[3];
       int x;
       while(m--)
       {
           scanf("%s",command);
           if(command[0]=='D')
           {
               scanf("%d",&x);
               q[cnt++] = x;
               Update(x,0,1);//pos,val,rt
           }
           else if(command[0]=='R')
           {
               x=q[--cnt];
               Update(x,1,1);
           }
           else
           {
               scanf("%d",&x);
               printf("%d\n",query_ans(x,1));
           }
       }
   }
   return 0;
}