HDU-1540 Tunnel Warfareセグメントツリー

http://acm.hdu.edu.cn/showproblem.php?pid=1540
問題は線分に対して,D xはx点を破壊し,Rは最近破壊された点を回復し,Q xはx点を中心とした両端を尋ねる最長の連続区間を表す.2时间変更して、ついにAが落ちて、血を吐いて、特に杭电のテストデータ、1つの点は何度も破壊することができて、この小さい日本の鬼子もあまりにも悪いでしょう、更にもし1つの点が何度も破壊するならば、八路军のおじさんも何度も修理しなければならなくて、问题の意味は実际と合わないで、またPOJの厚い道です.
この問題は2つの部分に分けて、まず1本の線分の木を創立して、この線分の木は少し情報を残すべきです:
1.当該区間の左連続長さ、右連続長さ2.当該区間の被覆状況(すなわち、破壊が発生していないか否か)これは線分木が空間的に時間を入れ替える場所である
そして連続する区間の長さを求め、結果を出す手順はこうです.
A.まずこのノード(x)が破壊されたかどうかを判定し、破壊が直接0 Bに戻る.破壊されていなければ、1~x-1の右連続段とx+1~Nの左連続段に自分自身の1を加える
R操作については、stackを用意すればいいので、杭電の1つの点が何度も破壊されることに注意してください.
コードは次のとおりです.

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <stack>
#define MAXN 50005
using namespace std;

struct Node
{
    int l, r;
    int lenl, lenr, cover;
}seg[MAXN*3];

char rec[MAXN];

void creat(int f, int l, int r)
{
    int mid = (l+r)>>1;
    seg[f].l = l, seg[f].r = r; 
    seg[f].lenl = r-l;
    seg[f].lenr = r-l;
    seg[f].cover = 1;
    if (r - l > 1)
    {
        creat(f<<1, l, mid);
        creat(f<<1|1, mid, r);
    } 
}

void modify(int f, int l, int r, int val)
{
    int mid = (seg[f].l + seg[f].r)>>1;
    if (seg[f].l == l && r == seg[f].r)
    {
        seg[f].lenl = seg[f].lenr = val;
        seg[f].cover = val;
    }
    else if (seg[f].r - seg[f].l > 1)
    {
        if (seg[f].cover == 1)
        {  // lazy   
            seg[f<<1].cover = seg[f].cover;
            seg[f<<1|1].cover = seg[f].cover;
            seg[f].cover = 0;
        }
        if (r <= mid)
            modify(f<<1, l, r, val);
        else if (l >= mid)
            modify(f<<1|1, l, r, val);
        else
        {
            modify(f<<1, l, mid, val);
            modify(f<<1|1, mid, r, val);
        } 
        seg[f].lenl = seg[f<<1].lenl;
        seg[f].lenr = seg[f<<1|1].lenr;
        if (seg[f<<1].cover == 1)
            seg[f].lenl += seg[f<<1|1].lenl;
        if (seg[f<<1|1].cover == 1)
            seg[f].lenr += seg[f<<1].lenr;
        //            
        seg[f].cover = seg[f<<1].cover && seg[f<<1|1].cover;
        //   cover  
    }
}

int lquery(int f, int l, int r)
{
    int mid = (seg[f].l+seg[f].r)>>1;
    if (seg[f].l == l && r == seg[f].r)
    {
        return seg[f].lenl;
    }
    else if (seg[f].r - seg[f].l > 1)
    {
        if (r <= mid) 
            return lquery(f<<1, l, r); 
        else if (l >= mid)
            return lquery(f<<1|1, l, r); 
        else
        {
            int c = lquery(f<<1, l, mid);
            if (c == mid-l)
            {
                c += lquery(f<<1|1, mid, r);
            }
            return c;
        }
    }
    else return 0;
}


int rquery(int f, int l, int r)
{
    int mid = (seg[f].l+seg[f].r)>>1;
    if (seg[f].l == l && r == seg[f].r)
    {
        return seg[f].lenr;
    }
    else if (seg[f].r - seg[f].l > 1)
    {
        if (r <= mid)
            return rquery(f<<1, l, r);
        else if (l >= mid)
            return rquery(f<<1|1, l, r);
        else
        {
            int c = rquery(f<<1|1, mid, r);
            if (c == r-mid)
            {
                c += rquery(f<<1, l, mid);
            }
            return c;
        }
    }
    else
        return 0;
}

int main()
{
    int N, M, x;
    char op[10];
    while (scanf("%d %d", &N, &M) == 2)
    {
        stack<int>stk;
        memset(rec, 1, sizeof (rec));
        creat(1, 1, N+1);
        for (int i = 0; i < M; ++i)
        {
            scanf("%s", op);
            if (op[0] == 'R')
            {
                if (!stk.empty())
                {
                    int c = stk.top();
                    rec[c] = 1;
                    stk.pop();
                    modify(1, c, c+1, 1);
                }
            }
            else if (op[0] == 'D')
            {
                scanf("%d", &x); 
                rec[x] = 0;
                stk.push(x);
                modify(1, x, x+1, 0); 
            }
            else
            {
                scanf("%d", &x);
                if (rec[x] == 0)
                    printf("0
");
                else
                    printf("%d
", lquery(1, x+1, N+1)+rquery(1, 1, x)+1);
            }
        }
    }
    return 0;
}