I - Tunnel Warfare HDU 1540（线段树+最大的连续区间）

I - Tunnel Warfare

Time Limit:2000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u

Submit Status Practice HDU 1540

Description

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!

Input

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

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

Sample Input

7 9

D 3

D 6

D 5

Q 4

Q 5

R

Q 4

R

Q 4

Sample Output

1

2

4

http://www.cnblogs.com/scau20110726/archive/2013/05/07/3065418.html

这篇文章的分析很好，但是查询没有说，

#include<bits/stdc++.h>
//#include<iostream>
//#include<cmath>
//#include<cstring>
//#include<string>
//#include<cstdlib>
//#include<cstdio>
//#include<map>
//#include<algorithm>
using namespace std;
template<class T>inline T read(T&x)
{
    char c;
    while((c=getchar())<=32)if(c==EOF)return -1;
    bool ok=false;
    if(c=='-')ok=true,c=getchar();
    for(x=0; c>32; c=getchar())
        x=x*10+c-'0';
    if(ok)x=-x;
    return 1;
}
template<class T> inline T read_(T&x,T&y)
{
    return read(x)!=-1&&read(y)!=-1;
}
template<class T> inline T read__(T&x,T&y,T&z)
{
    return read(x)!=-1&&read(y)!=-1&&read(z)!=-1;
}
template<class T> inline void write(T x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}
template<class T>inline void writeln(T x)
{
    write(x);
    putchar('\n');
}
//-------ZCC IO template------
const int maxn=50010;
const double inf=999999999;
#define lson (rt<<1),L,M
#define rson (rt<<1|1),M+1,R
#define M ((L+R)>>1)
#define For(i,t,n) for(int i=(t);i<(n);i++)
typedef long long  LL;
typedef double DB;
#define bug printf("---\n");

struct node
{
    int tlen,llen,rlen;//tlen表示当前区间的最大连续长度，llen表示当前区间左端点的连续长度，rlen表示当前区间右端点的连续长度
}p[maxn<<2];
int stak[maxn],top;//本题栈很简单，直接用数组模拟即可

void build(int rt,int L,int R)
{
    p[rt].llen=p[rt].rlen=p[rt].tlen=R-L+1;//建立树，开始时都是连续的
    if(L==R)return ;
    build(lson);
    build(rson);
}

void update(int rt,int L,int R,int i,int v)
{
    if(L==R)
    {
        p[rt].llen=p[rt].rlen=p[rt].tlen=v;//到达叶子结点直接更新
        return ;
    }

    if(i<=M)update(lson,i,v);
    else update(rson,i,v);

    p[rt].llen=p[rt<<1].llen;//维护父亲的rlen，llen，tlen，画个图就能理解
    p[rt].rlen=p[rt<<1|1].rlen;
    p[rt].tlen=max(max(p[rt<<1].tlen,p[rt<<1|1].tlen),p[rt<<1].rlen+p[rt<<1|1].llen);

    if(p[rt<<1].tlen==M-L+1)//关键的地方，如果左儿子区间全部是连续的，那么他父亲的左端点的连续长度就要加上该父亲右儿子左端点的连续长度
        p[rt].llen+=p[rt<<1|1].llen;
    if(p[rt<<1|1].tlen==R-M)//右儿子全部连续，父亲的右端点的连续长度，就要加上左儿子的右端点的连续长度
        p[rt].rlen+=p[rt<<1].rlen;//如果觉得绕，画个图，很清晰
}

int query(int rt,int L,int R,int pos)
{
    if(L==R||p[rt].tlen==0||p[rt].tlen==R-L+1)
    {
        return p[rt].tlen;
    }
    if(pos<=M)
    {
        if(p[rt<<1].rlen>=M-pos+1)//如果查询到POS在的左儿子区间是全部连续的，那么就要加上右儿子的左端点的连续，下面同理
            return query(lson,pos)+query(rson,M+1);
        else
            return query(lson,pos);
    }
    else
    {
        if(p[rt<<1|1].llen>=pos-M)
            return query(rson,pos)+query(lson,M);
        else
            return query(rson,pos);
    }
}

int main()
{
    //freopen("in.txt","r",stdin);
    int n,m,i,j,k,t;
    while(read_(n,m))
    {
        build(1,1,n);
        char op[2];
        top=0;
        while(m--)
        {
            scanf("%s",op);
            if(op[0]=='D')
            {
                read(k);
                stak[top++]=k;
                update(1,1,n,k,0);
            }
            else if(op[0]=='Q')
            {
                read(k);
                writeln(query(1,1,n,k));
            }
            else
            {
                k=stak[--top];
                update(1,1,n,k,1);
            }
        }
    }
    return 0;
}