青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

隨筆 - 97, 文章 - 22, 評論 - 81, 引用 - 0
數據加載中……

PKU 2892 Tunnel Warfare

題目鏈接:http://poj.org/problem?id=2892
/*
題意:
    給出M(M <= 50000)組操作,每組操作的形式如下:
1 D x: 將第x個村莊摧毀
2 Q x: 詢問和第x個村莊直接或者間接連接的村莊數目
3 R: 修復上一個被摧毀的村莊

解法:
線段樹 或者 樹狀數組

思路:
    線段樹染色問題,和ZJU 2301 Color the Ball類似,也是尋找最長連
續區間。但是這題要簡單的多,因為插入的時候是對點操作,不需要用到
lazy標記,線段樹中可以保存如下信息:

    enum eKind {
        EK_BLACK = 0,
        EK_WHITE = 1,
    };

    int root, l, r;   
    int lMax;          // 包含左區間的連續空閑區間的最大值
    int rMax;          // 包含右區間的連續空閑區間的最大值
    int mMax;          // 當前結點管轄區間的最大值

    首先來看下問題對應的操作,題目中有兩種插入,一個是插入一個摧毀
的村莊,另一個是插入一個修復的村莊,其實原理是一樣的。只不過這兩種
類型更新lMax,rMax,mMax的時候稍有不同,每次插入到線段樹元區間時,
根據插入的eKind類型填充mMax、lMax、rMax的信息,否則更新他們的結點
信息,然后遞歸左右兒子,繼續插入操作,遞歸返回時我們用以下函數從左
右兒子中得到當前結點的信息:
void UpdateBy(Tree* ls, Tree* rs);
之所以把它寫成函數是因為這里的處理比較麻煩,很容易出錯,并且需要
調用多次,這個函數的作用就是通過左右兒子的信息填充本身的信息。
信息一多,處理的時候就要極為小心,因為很容易出錯。
lMax表示當前結點的包含左閉區間的最優解。
rMax表示當前結點的包含右閉區間的最優解。
mMax則是當前區間的最優解。
這樣我們就可以通過傳遞性在兒子結點的屬性都得知的情況下將父親的值
計算出來,最后遞歸到根結點。具體的計算過程可以自己畫棵樹看一下,
    然后是查詢操作,查詢的話首先來看遞歸出口,我們用兩個引用來表示
當前查到的信息是否左連通以及是否右連通,那么如果到元區間的時候當前
點的mMax是0,那么直接左右連通標記都標記為false,否則為true。如果不
是元區間,則判斷當前點在左兒子還是右兒子,如果在左兒子,那么遞歸左
右子,回歸時根據返回的引用值判斷當前是否右連通,如果右連通,那么將
右兒子的lMax值加到答案上來,再判斷lMax是否等于右兒子的len,如果不
相等說明下次回歸上去的時候必然不是右連通,標記置為false,對于右兒子
的情況做相同處理即可。回歸到根結點就是最后的答案了。
    這題還可以用樹狀數組來做,寫起來也比較方便,還是利用成段求和來
統計當前點區間內的K大值,K值用二分枚舉即可。
*/

#include 
<iostream>

using namespace std;

#define maxn 50010

enum eKind {
    EK_BLACK 
= 0,
    EK_WHITE 
= 1,
}
;

struct Tree {
    
int root, l, r;
    
int lMax, rMax, mMax;

    
void CoverBy(eKind ek);
    
void UpdateBy(Tree* ls, Tree* rs);

    
int len() {
        
return r - l + 1;
    }

}
T[4*maxn];

void Build(int p, int l, int r) {
    T[p].root 
= p;
    T[p].l 
= l;
    T[p].r 
= r;
    T[p].rMax 
= T[p].lMax = T[p].mMax = T[p].len();
    
if(l == r)
        
return ;
    
int mid = (l + r) >> 1;
    Build(p
<<1, l, mid);
    Build(p
<<1|1, mid+1, r);
}


int MMax(int a, int b) {
    
return a > b ? a : b;
}


int MMax(int a, int b, int c, int d) {
    
return MMax( MMax(a, b), MMax(c, d) );
}


void Tree::UpdateBy(Tree* ls, Tree* rs) {
    lMax 
= ls->lMax; if(lMax == ls->len()) lMax += rs->lMax;
    rMax 
= rs->rMax; if(rMax == rs->len()) rMax += ls->rMax;
    mMax 
= MMax(lMax, rMax);
    mMax 
= MMax(mMax, ls->mMax, rs->mMax, ls->rMax + rs->lMax);
}


void Tree::CoverBy(eKind ek) {
    mMax 
= lMax = rMax = (ek==EK_WHITE) ? len() : 0;
}


void Insert(int p, int pos, eKind ek) {
    
if(pos > T[p].r || pos < T[p].l)
        
return ;
    
if(T[p].l == pos && pos == T[p].r) {
        T[p].CoverBy(ek);
        
return ;
    }

    Insert(p
<<1, pos, ek);
    Insert(p
<<1|1, pos, ek);

    T[p].UpdateBy(
&T[p<<1], &T[p<<1|1]);
}


int Query(int p, int pos, bool& lc, bool& rc) {
    
if(T[p].l == pos && pos == T[p].r) {
        lc 
= rc = T[p].mMax;
        
return T[p].mMax;
    }


    
int x;
    
if(pos <= T[p<<1].r) {
        x 
= Query(p<<1, pos, lc, rc);
        
if(rc) {
            x 
+= T[p<<1|1].lMax;
            
if(T[p<<1|1].lMax < T[p<<1|1].len())
                rc 
= false;
        }

    }
else {
        x 
= Query(p<<1|1, pos, lc, rc);
        
if(lc) {
            x 
+= T[p<<1].rMax;
            
if(T[p<<1].rMax < T[p<<1].len())
                lc 
= false;
        }

    }

    
return x;
}


int n, m;
int stack[maxn], top;
int main() {
    
char str[5];
    
int x;
    
while(scanf("%d %d"&n, &m) != EOF) {
        Build(
11, n);
        top 
= 0;
        
while(m--{
            scanf(
"%s", str);
            
if(str[0== 'D'{
                scanf(
"%d"&stack[top]);
                Insert(
1, stack[top], EK_BLACK);
                top 
++;
            }
else if(str[0== 'R'{
                
if(top) {
                    top 
--;
                    Insert(
1, stack[top], EK_WHITE);
                }

            }
else {
                scanf(
"%d"&x);
                
// 左連通、右連通
                bool lc, rc;
                printf(
"%d\n", Query(1, x, lc, rc));
            }

        }

    }

    
return 0;
}

posted on 2011-04-07 12:31 英雄哪里出來 閱讀(1493) 評論(0)  編輯 收藏 引用 所屬分類: 線段樹樹狀數組

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲视频在线播放| 久久一区免费| 欧美三级小说| 久久精品最新地址| 久久激情中文| 夜久久久久久| 久久久99精品免费观看不卡| 欧美二区在线| 国产日本欧洲亚洲| 亚洲精品免费一二三区| 国产精品v一区二区三区 | 国产九九视频一区二区三区| 久久久综合网| 国产色爱av资源综合区| 亚洲国产精品高清久久久| 国产一区二区欧美日韩| 一本久久a久久免费精品不卡| 极品尤物一区二区三区| 亚洲男人av电影| 亚洲一区三区电影在线观看| 欧美二区在线| 欧美电影在线播放| 亚洲第一精品福利| 老色批av在线精品| 一本大道久久精品懂色aⅴ| 欧美成人福利视频| 久久久久国产精品一区| 欧美日韩国产成人| 久久免费黄色| 欧美mv日韩mv亚洲| 国产一区导航| 亚洲午夜黄色| 亚洲精品国产视频| 欧美国产精品劲爆| 亚洲国产精品第一区二区| 国产综合欧美| 欧美日韩精品三区| 日韩视频在线观看免费| 亚洲国产欧美久久| 久久福利精品| 女人天堂亚洲aⅴ在线观看| 国产一区二区中文| 久久米奇亚洲| 亚洲第一在线综合网站| 91久久精品美女高潮| 久久人91精品久久久久久不卡| 欧美一区国产一区| 亚洲国产高清aⅴ视频| 欧美日韩国产色站一区二区三区| 亚洲精品一区二区三区在线观看| 亚洲免费小视频| 伊人精品久久久久7777| 欧美日韩不卡视频| 久久久久国内| 99综合精品| 欧美丰满高潮xxxx喷水动漫| 亚洲午夜一区二区三区| 99热免费精品在线观看| 亚洲成色www8888| 国产日韩精品电影| 国产农村妇女精品一二区| 欧美人与禽性xxxxx杂性| 久久久精品2019中文字幕神马| 亚洲一区二区精品在线观看| 亚洲国产精品久久久久久女王| 欧美一区二区三区在线视频| 99国产精品| 91久久中文| 亚洲国产日韩欧美在线图片 | 欧美性一区二区| 欧美日韩999| 国产精品久久精品日日| 欧美日韩在线免费视频| 国产精品欧美日韩久久| 国产日韩精品一区二区三区在线| 欧美日韩一区二区三区四区五区| 久久综合精品国产一区二区三区| 亚洲伦理在线免费看| 欧美凹凸一区二区三区视频| 久久婷婷综合激情| 久久久免费精品视频| 久久躁日日躁aaaaxxxx| 老司机免费视频久久| 欧美国产一区二区| 亚洲影院在线| 久久aⅴ国产欧美74aaa| 欧美77777| 国产嫩草影院久久久久| 91久久久久久久久| 亚洲视频香蕉人妖| 欧美不卡视频一区发布| 亚洲欧美精品suv| 欧美四级伦理在线| 亚洲日本中文字幕| 久久久久久999| 亚洲视频欧美在线| 久久久久久夜精品精品免费| 欧美日韩ab片| 亚洲国内精品| 久久久久久一区二区| 日韩一级精品| 欧美激情久久久久久| 国外成人免费视频| 羞羞视频在线观看欧美| 亚洲激情视频网站| 欧美日韩免费| 99riav久久精品riav| 亚洲精品欧洲精品| 欧美日韩国产综合视频在线观看中文| 亚洲电影在线免费观看| 亚洲国产精品成人精品| 欧美福利一区二区| 艳妇臀荡乳欲伦亚洲一区| 91久久精品一区| 欧美视频在线观看免费| 亚洲一二三区在线观看| 99精品欧美一区二区三区综合在线| 蜜臀av国产精品久久久久| 国产在线不卡精品| 久久精品亚洲一区| 欧美亚洲免费电影| 依依成人综合视频| 欧美激情二区三区| 在线亚洲一区观看| 女主播福利一区| 91久久久久久久久| 亚洲国产成人久久| 欧美日韩免费看| 夜夜嗨av色一区二区不卡| 欧美国产高清| 欧美日韩视频一区二区三区| 亚洲人体影院| 免费观看在线综合| 欧美日韩中文字幕精品| 午夜天堂精品久久久久| 亚洲图片欧美日产| 国产亚洲一级高清| 欧美一区二区三区在线观看| 新67194成人永久网站| 亚洲高清自拍| 一区二区三区免费看| 国产亚洲欧美日韩精品| 亚洲欧洲精品成人久久奇米网| 国产精品久久7| 欧美69wwwcom| 国产精品福利在线观看| 麻豆精品精品国产自在97香蕉| 欧美日本簧片| 麻豆精品一区二区综合av| 国产精品高潮呻吟视频| 免费在线成人| 国产欧美一区二区三区视频| 91久久精品日日躁夜夜躁国产| 国产嫩草一区二区三区在线观看| 亚洲黑丝一区二区| 亚洲高清网站| 亚洲视频在线一区观看| 亚洲日本aⅴ片在线观看香蕉| 久久久久国产精品厨房| 欧美在线亚洲综合一区| 国产精品素人视频| 男女精品网站| 国产欧美日韩一区| 久久精品久久99精品久久| 久久福利毛片| 国产精品毛片在线| 欧美一级淫片aaaaaaa视频| 欧美亚洲尤物久久| 国产欧美一区二区视频| 亚洲欧美韩国| 久久永久免费| 欧美激情影院| 欧美中文字幕在线观看| 久久av在线| 国产精品自拍小视频| 欧美中文字幕视频| 欧美激情中文字幕一区二区| 亚洲国产精品va在看黑人| 欧美一区二区网站| 一级日韩一区在线观看| 欧美一级午夜免费电影| 国产精品成人一区二区三区夜夜夜| 久久激情中文| 亚洲女性喷水在线观看一区| 久久伊人免费视频| 在线一区二区三区做爰视频网站| 久久九九精品| 亚洲自拍啪啪| 91久久精品国产91性色tv| 国产精品视频大全| 欧美va天堂| 欧美一区二区三区在线观看视频| 亚洲国产精品嫩草影院| 另类综合日韩欧美亚洲| 亚洲欧洲综合| 91久久中文| 亚洲日本视频| 国产日韩在线亚洲字幕中文| 欧美经典一区二区| 欧美激情亚洲一区|