【树的路径剖分】点权型的处理办法、路径的衔接以及一些细节问题

Posted on 2012-01-12 20:44 Mato_No1 阅读(487) 评论(0)  编辑 收藏 引用 所属分类: BZOJ 、专题:数据结构动态模拟问题
【例题】[SDOI2011]染色（注：数据范围木有交代，应为：点数N<=105，操作数M<=105，所有的颜色C为整数且在[0, 109]之间。

一、树的路径剖分当中点权型（点上有权值而边上木有）的处理办法：
（1）找重链建线段树的时候，w0中存储tot+1个数，为该重链自上而下的各点的权值（例题中为颜色）；
（2）除了父边是轻边的叶结点之外，树中的每个结点都属于且仅属于一条重链（根据定义得到），所以，设目前待查路径的两个点（也就是路径的两端点）为a0和b0，其LCA设为LCA0，则a0上溯到LCA0的时候，先判定a0是不是一个父边是轻边的叶结点，如果是，就对它单独处理，并跳到a0的父结点处开始循环上溯，否则从a0开始循环上溯。上溯时，若UP[a0]木有超越LCA0则上溯到UP[a0]否则上溯到LCA0，找到a0和上溯到的点的ord，再在线段树中处理，处理完后，跳到a0的父结点处（这里一定要判定是不是根结点），如此循环，直到超越（等于都不行）LCA0为止（如果LCA0是根，则上溯到根结点后直接强退）。对于b0类似处理即可；
（3）改值的时候，对于父边是轻边的叶结点直接改，对于其它结点在其所在重链对应的线段树中改；

二、路径的衔接问题的处理办法：
例题中由于要统计颜色段数，涉及到各重链之间（包括LCA0附近）的衔接问题，这个问题在点权型和边权型树中的处理办法不同。
下面照样设目前待查路径的两个点（也就是路径的两端点）为a0和b0，其LCA设为LCA0。
（1）对于点权型树：
先考虑a0上溯到LCA0中的情况。在此过程中需要设置“最新点”（准确来说是最新点的权值，即颜色）x0，一开始给x0赋一个不可能存在的值（比如-1、INF等）。首先，如果a0是一个父边是轻边的叶结点，则特判过程中需要先将最新点设为a0（的权值），然后在上溯的时候，不断将最新点改为UP[a0]，每次跳到父结点的时候比较跳到的点与最新点之间的颜色是否相同来进行衔接。对于b0上溯到LCA0的情况类似。不过还有一个地方，就是LCA0附近的衔接，这个在点权型树的处理办法是：先将“a0->LCA0”与“B0->LCA0"当成两条链（显然都包括LCA0），分别处理后，将这两条链衔接起来，由于它们都包括LCA0，衔接处颜色必定相等，故直接减1即可（注意这只是对于本题而言，对于其它题目还是那句话“具体情况具体分析”）
（2）对于边权型树：
需要设置的是“最新边”（一开始最新边都是不存在的）。上溯过程中存在轻重边之分，对于轻边，直接将其与最新边衔接再将最新边改为这条边即可，对于重链，将其最后一条边（注意在线段树中是最右的，可在过程中记录）与最新边衔接，再将最新边改为这条重链的第一条边（线段树中最左的，同样可在过程中记录）即可。对于“a0->LCA0”与“B0->LCA0"的最右的边的衔接问题，直接比较即可。

三、一些易疵点和细节问题（新发现的，补充，见代码中标Attention的地方）：
（1）对于prepare的第4步，深搜的时候，不要把边的编号（st[i]）与点的编号（i、j）搞混了，回溯的条件应是st[i]==i而不是j==i；
（2）求LCA的时候一定不要忘了“b<a"的情况（要交换），另外LCA可以作为一个函数来搞，省得每个操作都写；
（3）上溯的时候，对于点权型，不要忘了初始的特判、循环终止条件（超越LCA0）以及跳到父结点时对根结点的处理；
（4）其实，各个操作的上溯过程是可以写成专门的函数的（当然本沙茶在本例题中木有这样做）；
（5）维护线段树中记录的信息的时候，别搞疵了（本沙茶一开始在opr0中忘了维护lc和rc……）；
（6）线段树下放标记的时候一定要判断有木有标记；
（7）关于LCA的求法，NZK神犇（Orz！！！）表示有不需要借助RMQ或者倍增，直接求的，关键是本沙茶还木有搞懂；
（8）调试技巧是很重要的，可以省去大量的读程序、对拍的时间，甚至可能不用对拍（不过本沙茶太若了还不能实现这一点）；

代码：
#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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理