首页 > ACM题库 > HDU-杭电 > HDU 1540 Tunnel Warfare-栈-[解题报告] C++
2013
12-12

HDU 1540 Tunnel Warfare-栈-[解题报告] C++

Tunnel Warfare

问题描述 :

During the War of Resistance Against Japan, tunnel warfare was carried out extensively in the vast areas of north China Plain. Generally speaking, villages connected by tunnels lay in a line. Except the two at the ends, every village was directly connected with two neighboring ones.

Frequently the invaders launched attack on some of the villages and destroyed the parts of tunnels in them. The Eighth Route Army commanders requested the latest connection state of the tunnels and villages. If some villages are severely isolated, restoration of connection must be done immediately!

输入:

The first line of the input contains two positive integers n and m (n, m ≤ 50,000) indicating the number of villages and events. Each of the next m lines describes an event.

There are three different events described in different format shown below:

D x: The x-th village was destroyed.

Q x: The Army commands requested the number of villages that x-th village was directly or indirectly connected with including itself.

R: The village destroyed last was rebuilt.

输出:

Output the answer to each of the Army commanders’ request in order on a separate line.

样例输入:

7 9
D 3
D 6
D 5
Q 4
Q 5
R
Q 4
R
Q 4

样例输出:

1
0
2
4

线段树

题意:一个长度为n的线段,下面m个操作

D x 表示将单元x毁掉

R  表示修复最后毁坏的那个单元

Q x  询问这个单元以及它周围有多少个连续的单元,如果它本身已经被毁坏了就是0

 

要记录单元被损坏的顺序,用一个栈就好了,毁坏就入栈,修复就出栈

说说思路,最难的是查询一个点附近有那些的连接着的区间

这需要在线段树记录三个信息,tlen,llen,rlen,这个记录和 poj 3667 Hotel 记录的意义是相同的 , tlen表示该节点内最长的可用区间的长度,llen表示最左端数起的区间长度,rlen表示从最右端数起的区间长度

对于一个点,看它是在当前区间的左半还是右半

在左半的话,看看是不是在右端的连续区间内,是的话,还要加上右半区间的左端连续区间。否则的话,只要计算它在左半区间的连接情况即可

在右半的话同理,看看是不是在左端的连续区间内,是的话,还要加上左半区间的右端连续区间。否则的话,只要计算它在右半区间的连接情况即可

 

所以需要时刻维护好每个节点的tlen,llen,rlen,在updata函数中,和 poj 3667 Hotel 的维护是一样的

 

 

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
#define lch(i) ((i)<<1)
#define rch(i) ((i)<<1|1)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 50010

struct node
{
    int l,r;
    int mark;
    int tlen,llen,rlen;
    int mid(){
        return (l+r)>>1;
    }
    int cal_len(){
        return r-l+1;
    }
    void updata_len(){
        tlen = llen = rlen = (mark ? 0 : cal_len());
    }
}t[4*N];

void build(int l , int r , int rt)
{
    t[rt].l = l; t[rt].r = r; 
    t[rt].mark = 0;
    t[rt].tlen = t[rt].llen = t[rt].rlen = t[rt].cal_len();
    if(l == r) return ;
    int mid = t[rt].mid();
    build(l , mid , lch(rt));
    build(mid+1 , r , rch(rt));
    return ;
}

void updata(int pos ,int val ,int rt)
{
    if(t[rt].l == t[rt].r)
    {
        t[rt].mark = val;
        t[rt].updata_len();
        return ;
    } 
    if(t[rt].mark != -1)
    {
        t[lch(rt)].mark = t[rch(rt)].mark = t[rt].mark;
        t[rt].mark = -1;
        t[lch(rt)].updata_len();
        t[rch(rt)].updata_len();
    }
    int mid = t[rt].mid();
    if(pos <= mid) //在左半
        updata(pos , val , lch(rt));
    else //在右半
        updata(pos , val , rch(rt));

    int temp = max(t[lch(rt)].tlen , t[rch(rt)].tlen);
    t[rt].tlen = max(temp , t[lch(rt)].rlen + t[rch(rt)].llen);
    t[rt].llen = t[lch(rt)].llen;
    t[rt].rlen = t[rch(rt)].rlen;
    if(t[lch(rt)].tlen == t[lch(rt)].cal_len())
        t[rt].llen += t[rch(rt)].llen;
    if(t[rch(rt)].tlen == t[rch(rt)].cal_len())
        t[rt].rlen += t[lch(rt)].rlen;
    return ;
}

int query(int pos , int rt)
{
    if(t[rt].l == t[rt].r || t[rt].tlen == 0 || t[rt].tlen == t[rt].cal_len())
        return t[rt].tlen;
    //上面的部分可以改变一下写法,看看时间会不会有明显的变化
    
    if(t[rt].mark != -1)
    {
        t[lch(rt)].mark = t[rch(rt)].mark = t[rt].mark;
        t[rt].mark = -1;
        t[lch(rt)].updata_len();
        t[rch(rt)].updata_len();
    }
    int mid = t[rt].mid();
    if(pos <= mid) //查询的点在左边 
    {
        int index = mid-t[lch(rt)].rlen+1;
        if(index <= pos) //包含在内
            return query(pos , lch(rt)) + query(mid+1 , rch(rt));
        else
            return query(pos , lch(rt));
    }
    else
    {
        int index = mid+t[rch(rt)].llen;
        if(pos <= index) //包含在内
            return query(mid , lch(rt)) + query(pos , rch(rt));
        else
            return query(pos , rch(rt));
    }
}

int main()
{
    int n,m;
    stack<int>sta;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        build(1,n,1);
        while(!sta.empty()) sta.pop();
        while(m--)
        {
            char op[5];
            int pos , len;
            scanf("%s",op);
            if(op[0] == 'R')
            {
                if(sta.empty()) continue;
                int pos = sta.top();
                sta.pop();
                updata(pos , 0 , 1);
            }
            else if(op[0] == 'D')
            {
                scanf("%d",&pos);
                sta.push(pos);
                updata(pos , 1 , 1);
            }
            else
            {
                scanf("%d",&pos);
                len = query(pos,1);
                printf("%d\n",len);
            }
        }
    }
    return 0;

}

 

解题报告转自:http://www.cnblogs.com/scau20110726/archive/2013/05/07/3066009.html


  1. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”

  2. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge