欧美三日本三级三级在线播放,欧美日韩视频第一区,亚洲美女网站

【樹(shù)的路徑剖分】點(diǎn)權(quán)型的處理辦法、路徑的銜接以及一些細(xì)節(jié)問(wèn)題

Posted on 2012-01-12 20:44 Mato_No1 閱讀(525) 評(píng)論(0) 編輯收藏引用所屬分類: BZOJ 、專題:數(shù)據(jù)結(jié)構(gòu)動(dòng)態(tài)模擬問(wèn)題

【例題】[SDOI2011]染色（注：數(shù)據(jù)范圍木有交代，應(yīng)為：點(diǎn)數(shù)N<=10⁵，操作數(shù)M<=10⁵，所有的顏色C為整數(shù)且在[0, 10⁹]之間。

一、樹(shù)的路徑剖分當(dāng)中點(diǎn)權(quán)型（點(diǎn)上有權(quán)值而邊上木有）的處理辦法：
（1）找重鏈建線段樹(shù)的時(shí)候，w0中存儲(chǔ)tot+1個(gè)數(shù)，為該重鏈自上而下的各點(diǎn)的權(quán)值（例題中為顏色）；
（2）除了父邊是輕邊的葉結(jié)點(diǎn)之外，樹(shù)中的每個(gè)結(jié)點(diǎn)都屬于且僅屬于一條重鏈（根據(jù)定義得到），所以，設(shè)目前待查路徑的兩個(gè)點(diǎn)（也就是路徑的兩端點(diǎn)）為a0和b0，其LCA設(shè)為L(zhǎng)CA0，則a0上溯到LCA0的時(shí)候，先判定a0是不是一個(gè)父邊是輕邊的葉結(jié)點(diǎn)，如果是，就對(duì)它單獨(dú)處理，并跳到a0的父結(jié)點(diǎn)處開(kāi)始循環(huán)上溯，否則從a0開(kāi)始循環(huán)上溯。上溯時(shí)，若UP[a0]木有超越LCA0則上溯到UP[a0]否則上溯到LCA0，找到a0和上溯到的點(diǎn)的ord，再在線段樹(shù)中處理，處理完后，跳到a0的父結(jié)點(diǎn)處（這里一定要判定是不是根結(jié)點(diǎn)），如此循環(huán)，直到超越（等于都不行）LCA0為止（如果LCA0是根，則上溯到根結(jié)點(diǎn)后直接強(qiáng)退）。對(duì)于b0類似處理即可；
（3）改值的時(shí)候，對(duì)于父邊是輕邊的葉結(jié)點(diǎn)直接改，對(duì)于其它結(jié)點(diǎn)在其所在重鏈對(duì)應(yīng)的線段樹(shù)中改；

二、路徑的銜接問(wèn)題的處理辦法：
例題中由于要統(tǒng)計(jì)顏色段數(shù)，涉及到各重鏈之間（包括LCA0附近）的銜接問(wèn)題，這個(gè)問(wèn)題在點(diǎn)權(quán)型和邊權(quán)型樹(shù)中的處理辦法不同。
下面照樣設(shè)目前待查路徑的兩個(gè)點(diǎn)（也就是路徑的兩端點(diǎn)）為a0和b0，其LCA設(shè)為L(zhǎng)CA0。
（1）對(duì)于點(diǎn)權(quán)型樹(shù)：
先考慮a0上溯到LCA0中的情況。在此過(guò)程中需要設(shè)置“最新點(diǎn)”（準(zhǔn)確來(lái)說(shuō)是最新點(diǎn)的權(quán)值，即顏色）x0，一開(kāi)始給x0賦一個(gè)不可能存在的值（比如-1、INF等）。首先，如果a0是一個(gè)父邊是輕邊的葉結(jié)點(diǎn)，則特判過(guò)程中需要先將最新點(diǎn)設(shè)為a0（的權(quán)值），然后在上溯的時(shí)候，不斷將最新點(diǎn)改為UP[a0]，每次跳到父結(jié)點(diǎn)的時(shí)候比較跳到的點(diǎn)與最新點(diǎn)之間的顏色是否相同來(lái)進(jìn)行銜接。對(duì)于b0上溯到LCA0的情況類似。不過(guò)還有一個(gè)地方，就是LCA0附近的銜接，這個(gè)在點(diǎn)權(quán)型樹(shù)的處理辦法是：先將“a0->LCA0”與“B0->LCA0"當(dāng)成兩條鏈（顯然都包括LCA0），分別處理后，將這兩條鏈銜接起來(lái)，由于它們都包括LCA0，銜接處顏色必定相等，故直接減1即可（注意這只是對(duì)于本題而言，對(duì)于其它題目還是那句話“具體情況具體分析”）
（2）對(duì)于邊權(quán)型樹(shù)：
需要設(shè)置的是“最新邊”（一開(kāi)始最新邊都是不存在的）。上溯過(guò)程中存在輕重邊之分，對(duì)于輕邊，直接將其與最新邊銜接再將最新邊改為這條邊即可，對(duì)于重鏈，將其最后一條邊（注意在線段樹(shù)中是最右的，可在過(guò)程中記錄）與最新邊銜接，再將最新邊改為這條重鏈的第一條邊（線段樹(shù)中最左的，同樣可在過(guò)程中記錄）即可。對(duì)于“a0->LCA0”與“B0->LCA0"的最右的邊的銜接問(wèn)題，直接比較即可。

三、一些易疵點(diǎn)和細(xì)節(jié)問(wèn)題（新發(fā)現(xiàn)的，補(bǔ)充，見(jiàn)代碼中標(biāo)Attention的地方）：
（1）對(duì)于prepare的第4步，深搜的時(shí)候，不要把邊的編號(hào)（st[i]）與點(diǎn)的編號(hào)（i、j）搞混了，回溯的條件應(yīng)是st[i]==i而不是j==i；
（2）求LCA的時(shí)候一定不要忘了“b<a"的情況（要交換），另外LCA可以作為一個(gè)函數(shù)來(lái)搞，省得每個(gè)操作都寫；
（3）上溯的時(shí)候，對(duì)于點(diǎn)權(quán)型，不要忘了初始的特判、循環(huán)終止條件（超越LCA0）以及跳到父結(jié)點(diǎn)時(shí)對(duì)根結(jié)點(diǎn)的處理；
（4）其實(shí)，各個(gè)操作的上溯過(guò)程是可以寫成專門的函數(shù)的（當(dāng)然本沙茶在本例題中木有這樣做）；
（5）維護(hù)線段樹(shù)中記錄的信息的時(shí)候，別搞疵了（本沙茶一開(kāi)始在opr0中忘了維護(hù)lc和rc……）；
（6）線段樹(shù)下放標(biāo)記的時(shí)候一定要判斷有木有標(biāo)記；
（7）關(guān)于LCA的求法，NZK神犇（Orz！！！）表示有不需要借助RMQ或者倍增，直接求的，關(guān)鍵是本沙茶還木有搞懂；
（8）調(diào)試技巧是很重要的，可以省去大量的讀程序、對(duì)拍的時(shí)間，甚至可能不用對(duì)拍（不過(guò)本沙茶太若了還不能實(shí)現(xiàn)這一點(diǎn)）；

代碼：

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 100001, MAXS = 20, INF = ~0U >> 2;
struct edge {
    int a, b, pre, next;
    bool Z;
} E0[MAXN << 2], E[MAXN << 2];
struct node {
    int lc, rc, seg, lch, rch, mr;
} T[MAXN << 2];
int n, m0, m, N, w[MAXN], Q[MAXN], FA[MAXN], DEP[MAXN], SZ[MAXN], UP[MAXN], ord[MAXN], w0[MAXN], tot[MAXN], root[MAXN];
int stk[MAXN], st[MAXN], A[MAXN << 1], FF[MAXN], A0[MAXN << 1][MAXS], LOG[MAXN << 1], l0, r0, x0, _x1, res;
bool vst[MAXN];
void init_d()
{
    re(i, n) E0[i].pre = E0[i].next = E[i].pre = E[i].next = i;
    m = m0 = n;
}
void add_edge0(int a, int b)
{
    E0[m0].a = a; E0[m0].b = b; E0[m0].pre = E0[a].pre; E0[m0].next = a; E0[a].pre = m0; E0[E0[m0].pre].next = m0++;
    E0[m0].a = b; E0[m0].b = a; E0[m0].pre = E0[b].pre; E0[m0].next = b; E0[b].pre = m0; E0[E0[m0].pre].next = m0++;
}
void add_edge(int a, int b)
{
    E[m].a = a; E[m].b = b; E[m].Z = 0; E[m].pre = E[a].pre; E[m].next = a; E[a].pre = m; E[E[m].pre].next = m++;
}
int mkt(int l, int r)
{
    int No = ++N; T[N].lc = w0[l]; T[N].rc = w0[r]; T[N].mr = INF;
    if (l == r) {T[N].seg = 1; T[N].lch = T[N].rch = 0;} else {
        int mid = l + r >> 1, l_r = mkt(l, mid), r_r = mkt(mid + 1, r);
        T[No].seg = T[T[No].lch = l_r].seg + T[T[No].rch = r_r].seg;
        if (w0[mid] == w0[mid + 1]) T[No].seg--;
    }
    return No;
}
void prepare()
{
    N = 0; re(i, n) vst[i] = 0; Q[0] = 0; FA[0] = -1; DEP[0] = 0; vst[0] = 1;
    int i, j, x, x0, maxsz, n0, tp;
    for (int front=0, rear=0; front<=rear; front++) {
        i = Q[front];
        for (int p=E0[i].next; p != i; p=E0[p].next) {
            j = E0[p].b;
            if (!vst[j]) {vst[j] = 1; Q[++rear] = j; FA[j] = m; DEP[j] = DEP[i] + 1; add_edge(i, j);}
        }
    }
    rre(i0, n) {
        i = Q[i0]; SZ[i] = 1; maxsz = -INF;
        for (int p=E[i].next; p != i; p=E[p].next) {
            j = E[p].b; SZ[i] += SZ[j];
            if (SZ[j] > maxsz) {maxsz = SZ[j]; x = p;}
        }
        if (SZ[i] > 1) E[x].Z = 1;
    }
    UP[0] = ord[0] = 0;
    re2(i0, 1, n) {
        i = Q[i0]; int p = FA[i];
        if (E[p].Z) {UP[i] = UP[E[p].a]; ord[i] = ord[E[p].a] + 1;} else {UP[i] = i; ord[i] = 0;}
        if (SZ[i] == 1 && E[p].Z) {
            n0 = ord[i]; j = UP[i];
            for (int k=i; k!=j; k=E[FA[k]].a) {tot[k] = ord[i] + 1; w0[n0--] = w[k];} tot[j] = ord[i] + 1; w0[0] = w[j];
            root[j] = mkt(0, ord[i]); for (int k=i; k!=j; k=E[FA[k]].a) root[k] = root[j];
        }
    }
    stk[tp = 0] = 0; A[0] = 0; n0 = 1; re(i, n) {st[i] = E[i].next; FF[i] = -1;} FF[0] = 0;
    while (tp >= 0) {
        i = stk[tp]; j = E[st[i]].b;
        if (st[i] == i) {                //Attention
            if (tp) A[n0++] = stk[tp - 1]; tp--;
        } else {
            A[n0++] = j; stk[++tp] = j; st[i] = E[st[i]].next;
            if (FF[j] == -1) FF[j] = n0 - 1;
        }
    }
    rre(i, n0) {
        A0[i][0] = A[i]; x = 1;
        re2(j, 1, MAXS) {
            x0 = x << 1;
            if (i + x0 <= n0) {A0[i][j] = DEP[A0[i][j - 1]] <= DEP[A0[i + x][j - 1]] ? A0[i][j - 1] : A0[i + x][j - 1]; x = x0;} else break;
        }
    }
    x = 1;
    re(i, MAXS) {
        x0 = x << 1;
        if (x0 <= n0) {re2(j, x, x0) LOG[j] = i; x = x0;} else {re2(j, x, n0) LOG[j] = i; break;}
    }
}
int LCA(int a1, int b1)
{
    int a = FF[a1], b = FF[b1], tmp;
    if (a > b) {tmp = a; a = b; b = tmp;}     //Attention
    int len = LOG[b - a];
    if (DEP[A0[a][len]] <= DEP[A0[b - (1 << len) + 1][len]]) return A0[a][len]; else return A0[b - (1 << len) + 1][len];
}
void dm(int No, int lch, int rch)
{
    int mr0 = T[No].mr;
    if (mr0 != INF) {            //Attention
        T[No].mr = INF;
        T[lch].mr = T[lch].lc = T[lch].rc = mr0; T[lch].seg = 1;
        T[rch].mr = T[rch].lc = T[rch].rc = mr0; T[rch].seg = 1;
    }
}
void opr0(int l, int r, int No)
{
    if (l >= l0 && r <= r0) {T[No].mr = T[No].lc = T[No].rc = x0; T[No].seg = 1;} else {
        int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch; dm(No, lch, rch);
        if (mid >= l0) opr0(l, mid, lch);
        if (mid < r0) opr0(mid + 1, r, rch);
        T[No].lc = T[lch].lc; T[No].rc = T[rch].rc; T[No].seg = T[lch].seg + T[rch].seg;        //Attention
        if (T[lch].rc == T[rch].lc) T[No].seg--;
    }
}
void opr1(int l, int r, int No)
{
    if (l >= l0 && r <= r0) {
        res += T[No].seg; if (x0 == T[No].lc) res--; x0 = T[No].rc;
        if (_x1 == INF) _x1 = T[No].lc;
    } else {
        int mid = l + r >> 1, lch = T[No].lch, rch = T[No].rch; dm(No, lch, rch);
        if (mid >= l0) opr1(l, mid, lch);
        if (mid < r0) opr1(mid + 1, r, rch);
    }
}
int main()
{
    int M, a0, b0, w1, LCA0, U0, x1;
    char ch;
    scanf("%d%d", &n, &M); init_d();
    re(i, n) scanf("%d", &w[i]);
    re(i, n-1) {scanf("%d%d", &a0, &b0); add_edge0(--a0, --b0);}
    prepare();
    re(i, M) {
        scanf("\n"); ch = getchar();
        if (ch == 'C') {
            scanf("%d%d%d", &a0, &b0, &w1); LCA0 = LCA(--a0, --b0);
            if (SZ[a0] == 1 && !E[FA[a0]].Z) {w[a0] = w1; a0 = E[FA[a0]].a;}     //Attention
            while (DEP[a0] >= DEP[LCA0]) {    //Attention
                U0 = UP[a0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[a0]; x0 = w1; opr0(0, tot[a0] - 1, root[a0]);
                if (DEP[U0] >= DEP[LCA0]) a0 = U0; else a0 = LCA0;
                if (FA[a0] != -1) a0 = E[FA[a0]].a; else break;        //Attention
            }
            if (SZ[b0] == 1 && !E[FA[b0]].Z) {w[b0] = w1; b0 = E[FA[b0]].a;}     //Attention
            while (DEP[b0] >= DEP[LCA0]) {    //Attention
                U0 = UP[b0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[b0]; x0 = w1; opr0(0, tot[b0] - 1, root[b0]);
                if (DEP[U0] >= DEP[LCA0]) b0 = U0; else b0 = LCA0;     //Attention
                if (FA[b0] != -1) b0 = E[FA[b0]].a; else break;
            }
        } else {
            scanf("%d%d", &a0, &b0); LCA0 = LCA(--a0, --b0); res = 0; x1 = INF;  //Attention
            if (SZ[a0] == 1 && !E[FA[a0]].Z) {res++; x1 = w[a0]; a0 = E[FA[a0]].a;}
            while (DEP[a0] >= DEP[LCA0]) {   //Attention
                U0 = UP[a0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[a0]; x0 = _x1 = INF; opr1(0, tot[a0] - 1, root[a0]);
                if (x1 == x0) res--; x1 = _x1;
                if (DEP[U0] >= DEP[LCA0]) a0 = U0; else a0 = LCA0;
                if (FA[a0] != -1) a0 = E[FA[a0]].a; else break;   //Attention
            }
            x1 = INF;
            if (SZ[b0] == 1 && !E[FA[b0]].Z) {res++; x1 = w[b0]; b0 = E[FA[b0]].a;}  //Attention
            while (DEP[b0] >= DEP[LCA0]) {   //Attention
                U0 = UP[b0]; if (DEP[U0] >= DEP[LCA0]) l0 = 0; else l0 = ord[LCA0]; r0 = ord[b0]; x0 = _x1 = INF; opr1(0, tot[b0] - 1, root[b0]);
                if (x1 == x0) res--; x1 = _x1;
                if (DEP[U0] >= DEP[LCA0]) b0 = U0; else b0 = LCA0;
                if (FA[b0] != -1) b0 = E[FA[b0]].a; else break;   //Attention
            }
            printf("%d\n", --res);
        }
    }
    return 0;
}

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: 【AHOI2013復(fù)仇】?jī)傻烙嘘P(guān)刪邊后最短路徑維護(hù)的猥瑣題【AHOI2013復(fù)仇】BZOJ2165 【AHOI2013復(fù)仇】?jī)傻繪IS模型題總結(jié) 【樹(shù)的路徑剖分】點(diǎn)權(quán)型的處理辦法、路徑的銜接以及一些細(xì)節(jié)問(wèn)題最近在BZOJ上的刷題總結(jié)

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

Mato is No.1

留言簿(21)

隨筆分類

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

【樹(shù)的路徑剖分】點(diǎn)權(quán)型的處理辦法、路徑的銜接以及一些細(xì)節(jié)問(wèn)題