POJ 2892 Tunnel Warfare || HDU 1540(树状数组+二分 || 线段树的单点更新+区间查询)

时间:2021-08-30 04:16:52

点我看题目

题意 :N个村子连成一条线,相邻的村子都有直接的地道进行相连,不相连的都由地道间接相连,三个命令,D x,表示x村庄被摧毁,R  ,表示最后被摧毁的村庄已经重建了,Q x表示,与x直接或间接相连的村庄有多少个,当然包括他自己。

思路 :这是一道用线段树,树状数组,还有STL都可以做的题。。。。因为用线段树的更新什么的太麻烦,。。。。。所以我用了树状数组

POJ 2892 Tunnel Warfare || HDU 1540(树状数组+二分 || 线段树的单点更新+区间查询)POJ 2892 Tunnel Warfare || HDU 1540(树状数组+二分 || 线段树的单点更新+区间查询)
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int maxn = 501252 ;
int tree[maxn],data[maxn]  ;
bool vis[maxn] ;
int  n , m ;

int lowbit(int x)
{
    return (x & (-x)) ;
}

void add(int x,int value)
{
    for(int i = x ; i <= n ; i += lowbit(i))
        tree[i] += value ;
}
int get(int x)
{
    int sum = 0 ;
    for(int i = x ; i ; i -= lowbit(i))
        sum += tree[i] ;
    return sum ;
}

int binary_search(int v)
{
    int l = 1 , r = n+1 ,i = n+2;//n+2是为了防止最后一个村庄找不到的时候没有返回值
    while(l <= r)
    {
        int mid = (l + r) >> 1 ;
        if(get(mid) >= v)
        {
            r = mid-1 ;
            i = mid ;
        }
        else l = mid+1 ;
    }
    return i ;
}
int main()
{
    while(~scanf("%d %d",&n,&m))
    {
        int a , i = 0;
        while(m--)
        {
            getchar() ;
            char ch ;
            scanf("%c",&ch) ;
            if(ch == 'D')
            {
                scanf("%d",&a) ;
                data[++i] = ++a ;//被摧毁的村庄都存在data数组里
                vis[a] = true ;
                add(a,1) ;
            }
            else if(ch == 'Q')
            {
                scanf("%d",&a) ;
                a ++ ;
                if(vis[a]) printf("0\n") ;
                else
                {
                    int sum1,sum2 ;
                    a = get(a) ;
                    sum1 = binary_search(a) ;
                    sum2 = binary_search(a+1) ;
                    printf("%d\n",sum2-sum1-1) ;
                }
            }
            else if(ch == 'R')
            {
                a = data[i--] ;
                vis[a] = false ;
                add(a,-1) ;
            }
        }
    }
    return 0;
}
View Code

 以前用树状数组做的,现在用线段树做的,因为没有初始化WA到死,杭电上是多组数据,所以一开始也WA了,因为每次重建的时候建的是最后一个村子,将被摧毁的村子放入栈中就可以了,然后要标记一下,所有的村子存在即为0,摧毁了即为1,更新用单点,查询用区间,查询x村子时,寻找左边离他最近的那个被摧毁的村庄即1,以及最右边那个被摧毁的村庄,然后两个相减加1即为结果,但是如果他本身就被摧毁了直接是0。

POJ 2892 Tunnel Warfare || HDU 1540(树状数组+二分 || 线段树的单点更新+区间查询)POJ 2892 Tunnel Warfare || HDU 1540(树状数组+二分 || 线段树的单点更新+区间查询)
  1 //1540
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <iostream>
  5 
  6 using namespace std ;
  7 
  8 int lz[51000*4],p[51000 * 4],vis[51000 * 4],stk[51000*4] ;
  9 
 10 void pushup(int rt)
 11 {
 12     p[rt] = p[rt << 1] + p[rt << 1 | 1] ;
 13 }
 14 void update(int x,int l,int r,int rt,int sc)
 15 {
 16     if(l == r)
 17     {
 18         p[rt] = sc ;
 19         return ;
 20     }
 21     int mid = (l+r) >> 1 ;
 22     if(x <= mid)
 23         update(x,l,mid,rt << 1 , sc) ;
 24     else
 25         update(x,mid+1,r,rt << 1 | 1 ,  sc) ;
 26     pushup(rt) ;
 27 }
 28 int query(int L,int R,int l,int r,int rt)
 29 {
 30     int sum = 0 ;
 31     if(L <= l && r <= R)
 32     {
 33         return p[rt] ;
 34     }
 35     int mid = (l+r) >> 1 ;
 36     if(mid >= L)
 37         sum += query(L,R,l,mid,rt << 1) ;
 38     if(mid < R)
 39         sum += query(L,R,mid+1,r,rt << 1 | 1) ;
 40     return sum ;
 41 }
 42 int findd(int l,int r,int x,int rt)
 43 {
 44     if(l == r)
 45     {
 46         return l;
 47     }
 48     int mid = (l+r) >> 1 ;
 49     if(x <= p[rt << 1])
 50         return findd(l,mid,x,rt << 1) ;
 51     else return findd(mid+1,r,x-p[rt << 1],rt << 1 | 1) ;
 52 }
 53 int main()
 54 {
 55     int n, m,x;
 56     char ch[3] ;
 57     while(~scanf("%d %d",&n,&m))
 58     {
 59         int top = 0 ;
 60         memset(p,0,sizeof(p)) ;
 61         memset(vis,0,sizeof(vis)) ;
 62         for(int i = 0 ; i < m ; i++)
 63         {
 64             scanf("%s",ch)  ;
 65             if(ch[0] == 'R')
 66             {
 67                 if(top != 0)
 68                 {
 69                     vis[stk[top-1]] = 0 ;//村庄存在即为0,被摧毁即为1
 70                     update(stk[top-1],1,n,1,0) ;
 71                     top-- ;
 72                 }
 73             }
 74             else if(ch[0] == 'D')
 75             {
 76                 scanf("%d",&x) ;
 77                 vis[x] = 1 ;
 78                 stk[top++] = x ;
 79                 update(x,1,n,1,1) ;
 80             }
 81             else if(ch[0] == 'Q')
 82             {
 83                scanf("%d",&x) ;
 84                 if(vis[x])
 85                 {
 86                     printf("0\n") ;
 87                     continue ;
 88                 }
 89                 int l,r ;
 90                 int l1 = query(1,x,1,n,1) ;//x村庄左边的和
 91                 if(l1 == 0)//如果和为0,说明x村庄左边全部都存在
 92                     l = 1 ;
 93                 else l = findd(1,n,l1,1)+1;//找出左边离x最近的那个一,既不存在的那个村庄
 94                 int r1 = query(x,n,1,n,1) ;
 95                 if(r1 == 0)
 96                     r = n;
 97                 else r = findd(1,n,l1+1,1)-1 ;
 98                 printf("%d\n",r-l+1) ;
 99             }
100         }
101     }
102     return 0 ;
103 }
View Code