ZJOI2011《道馆之战》解题报告 - By LTL
ltl2011/06/08软件综合 IP:福建
感觉很好的一道题目,可以算是树链剖分中比较值得思考的题目之一。

题目描述:
口袋妖怪(又名神奇宝贝或宠物小精灵)红/蓝/绿宝石中的水系道馆需要经过三个冰地才能到达馆主的面前,冰地中的每一个冰块都只能经过一次。当一个冰地上的所有冰块都被经过之后,到下一个冰地的楼梯才会被打开。

当走出第三个冰地之后,就可以与馆主进行道馆战了。

馆主发现这个难度太小,导致经常有挑战者能通过,为了加大难度,将道馆分成了n个房间,每个房间中是两个冰块或障碍,表示一列冰地。任意两个房间之间均有且仅有一条路径相连,即这n个房间构成一个树状结构。

每个房间分成了A和B两个区域,每一区域都是一个薄冰块或者障碍物。每次只能移动到相邻房间的同一类区域(即若你现在在这个房间的A区域,那么你只能移动到相邻房间的A区域)或这个房间的另一区域。

现在挑战者从房间u出发,馆主在房间v,那么挑战者只能朝接近馆主所在房间的方向过去。一开始挑战者可以在房间u的任意一个冰块区域内。如果挑战者踩过的冰块数达到了最大值(即没有一种方案踩过的冰块数更多了),那么当挑战者走到最后一个冰块上时,他会被瞬间传送到馆主面前与馆主进行道馆战。

自从馆主修改规则后已经经过了m天,每天要么是有一个挑战者来进行挑战,要么就是馆主将某个房间进行了修改。对于每个来的挑战者,你需要计算出他若要和馆主进行战斗需要经过的冰块数。

题目简述:
题目描述中的背景实在是太长了……我就不吐槽它了……
n个点的树,每个节点由两个区域组成,均为空地或者障碍,在同一个节点内可以随意走动,但每个空地最多只能经过一次,两个节点之间移动则只能在两点的相同区域之间进行。m个操作:
1.    修改一个节点的布局;
2.    查询从u向v方向走最长能走多长(不一定要到v)。
n≤30000,m≤80000。

Time Limit:4s

关键字:树链剖分

算法描述:
很明显是树链剖分,但是重点就在于要维护什么。
对于一段路径,我们关心的只是从路径一端的某个区域向另一端的某个区域走可以走多远,所以对于每个点要记录3个值:f[0..1][0..1],l[0..1],r[0..1],分别表示两端某两个区域之间的最长路,从左端点某个区域出发的最长路和右端点的。。这样,就可以在线段树很方便地进行维护。由于维护的关键字较多,本题代码较长(也许是我写得丑……)。

总结&收获:
线段树中的修改操作刚开始由于错误地使用了线段树中的标号(而不是对应在原树中的点标号),导致Wa了很久。在以后写树链剖分的时候需加以注意!

My Code:

/*
Author: LTL
Data: 2011-6-8
*/

#include <iostream>
#include <memory.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>

#define InputFileName        "XXXXXXX"
#define OutputFileName        "Data.out"
#define Max(a, b)            (a > b ? a : b)

using namespace std;

const int MaxN = 31000, MaxE = MaxN*2, oo = 1000000000;

int n, m, Next[MaxE], v[MaxE], Head[MaxN], ENum, Total, d[MaxE][20], Depth[MaxN], Size[MaxN], Heavy[MaxN], Father[MaxN], Pos[MaxN];
bool View[MaxN];
int Seq[MaxN], STNum[MaxN], STPos[MaxN], STSize[MaxN], STTail[MaxN], Root[MaxN], STTotal, Left[MaxN*4], Right[MaxN*4], f[MaxN*4][2][2], L[MaxN*4][2], R[MaxN*4][2];
char a[MaxN][3];

inline void AddEdge(const int x, const int y)
{
    Next[++ENum] = Head[x];
    v[Head[x] = ENum] = y;
}

void Init()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i < n; ++i)
    {
        scanf("%d%d", &x, &y);
        AddEdge(x, y);
        AddEdge(y, x);
    }
    for (int i = 1; i <= n; ++i)
        scanf("%s", a[i]);
}

void DFS(const int t)
{
    View[t] = Size[t] = 1;
    d[Pos[t] = ++Total][0] = t;
    for (int i = Head[t]; i; i = Next[i])
        if (! View[v[i]])
        {
            Depth[v[i]] = Depth[t]+1;
            Father[v[i]] = t;
            DFS(v[i]);
            Size[t] += Size[v[i]];
            d[++Total][0] = t;
            if (! Heavy[t] || Size[v[i]] > Size[Heavy[t]])
                Heavy[t] = v[i];
        }
}

inline int RMQMin(const int x, const int y)
{
    return Depth[x] < Depth[y] ? x : y;
}

inline int LCA(int x, int y)
{
    if ((x = Pos[x]) > (y = Pos[y]))
        swap(x, y);
    const int k = (int)log2(y-x+1);
    return RMQMin(d[x][k], d[y-(1 << k)+1][k]);
}

inline void Combine(int c[2][2], int a[2][2], int b[2][2])
{
    int Res[2][2];
    Res[0][0] = Max(a[0][0]+b[0][0], a[0][1]+b[1][0]);
    Res[0][1] = Max(a[0][0]+b[0][1], a[0][1]+b[1][1]);
    Res[1][0] = Max(a[1][0]+b[0][0], a[1][1]+b[1][0]);
    Res[1][1] = Max(a[1][0]+b[0][1], a[1][1]+b[1][1]);
    c[0][0] = Max(Res[0][0], -oo);
    c[0][1] = Max(Res[0][1], -oo);
    c[1][0] = Max(Res[1][0], -oo);
    c[1][1] = Max(Res[1][1], -oo);
}

inline void CalcL(int c[2], int s[2][2], int a[2], int b[2])
{
    int r[2];
    r[0] = Max(s[0][0]+b[0], s[0][1]+b[1]);
    r[1] = Max(s[1][1]+b[1], s[1][0]+b[0]);
    c[0] = Max(r[0], a[0]);
    c[1] = Max(r[1], a[1]);
}

inline void CalcR(int c[2], int s[2][2], int a[2], int b[2])
{
    int r[2];
    r[0] = Max(a[0]+s[0][0], a[1]+s[1][0]);
    r[1] = Max(a[1]+s[1][1], a[0]+s[0][1]);
    c[0] = Max(r[0], b[0]);
    c[1] = Max(r[1], b[1]);
}

void Build(int &t, const int l, const int r)
{
    t = ++Total;
    if (l == r)
    {
        f[t][0][0] = a[Seq[l]][0] == '.' ? 1 : -oo;
        f[t][0][1] = f[t][1][0] = a[Seq[l]][0] == '.' && a[Seq[l]][1] == '.' ? 2 : -oo;
        f[t][1][1] = a[Seq[l]][1] == '.' ? 1 : -oo;
        L[t][0] = Max(f[t][0][0], f[t][0][1]);
        L[t][1] = Max(f[t][1][0], f[t][1][1]);
        L[t][0] = Max(L[t][0], 0);
        L[t][1] = Max(L[t][1], 0);
        memcpy(R[t], L[t], sizeof(L[t]));
        return;
    }
    const int mid = l+r >> 1;
    Build(Left[t], l, mid);
    Build(Right[t], mid+1, r);
    Combine(f[t], f[Left[t]], f[Right[t]]);
    CalcL(L[t], f[Left[t]], L[Left[t]], L[Right[t]]);
    CalcR(R[t], f[Right[t]], R[Left[t]], R[Right[t]]);
}

void Modify(const int t, const int l, const int r, const int p, const int k)
{
    if (l == r)
    {
        f[t][0][0] = a[k][0] == '.' ? 1 : -oo;
        f[t][0][1] = f[t][1][0] = a[k][0] == '.' && a[k][1] == '.' ? 2 : -oo;
        f[t][1][1] = a[k][1] == '.' ? 1 : -oo;
        L[t][0] = Max(f[t][0][0], f[t][0][1]);
        L[t][1] = Max(f[t][1][0], f[t][1][1]);
        L[t][0] = Max(L[t][0], 0);
        L[t][1] = Max(L[t][1], 0);
        memcpy(R[t], L[t], sizeof(L[t]));
        return;
    }
    const int mid = l+r >> 1;
    if (p <= mid)
        Modify(Left[t], l, mid, p, k);
    else
        Modify(Right[t], mid+1, r, p, k);
    Combine(f[t], f[Left[t]], f[Right[t]]);
    CalcL(L[t], f[Left[t]], L[Left[t]], L[Right[t]]);
    CalcR(R[t], f[Right[t]], R[Left[t]], R[Right[t]]);
}

void Query(const int t, const int l, const int r, const int x, const int y, int Res[2][2], int rL[2], int rR[2])
{
    if (x <= l && y >= r)
    {
        memcpy(Res, f[t], sizeof(f[t]));
        memcpy(rL, L[t], sizeof(L[t]));
        memcpy(rR, R[t], sizeof(R[t]));
        return;
    }
    const int mid = l+r >> 1;
    int tmp[2][2], tmpL[2], tmpR[2];
    if (x <= mid)
        Query(Left[t], l, mid, x, y, Res, rL, rR);
    if (y > mid)
        Query(Right[t], mid+1, r, x, y, tmp, tmpL, tmpR);
    if (x <= mid && y > mid)
    {
        CalcL(rL, Res, rL, tmpL);
        CalcR(rR, tmp, rR, tmpR);
        Combine(Res, Res, tmp);
    }
    else if (y > mid)
    {
        memcpy(Res, tmp, sizeof(tmp));
        memcpy(rL, tmpL, sizeof(tmpL));
        memcpy(rR, tmpR, sizeof(tmpR));
    }
}

void Prework()
{
    DFS(1);
    for (int i, j = 1, k = (int)log2(Total); j <= k; ++j)
        for (i = 1; i+(1 << j)-1 <= Total; ++i)
            d[i][j] = RMQMin(d[i][j-1], d[i+(1 << j-1)][j-1]);
    Total = 0;
    memset(View, 0, sizeof(View));
    for (int i = 1, j; i <= n; ++i)
        if (! View[i])
        {
            for (j = i; Heavy[j]; j = Heavy[j]);
            ++STTotal;
            for (View[j] = 1; Heavy[Father[j]] == j; View[j = Father[j]] = 1)
                Seq[STPos[j] = ++STSize[STNum[j] = STTotal]] = j;
            Seq[STPos[STTail[STTotal] = j] = ++STSize[STNum[j] = STTotal]] = j;
            Build(Root[STTotal], 1, STSize[STTotal]);
        }
}

void Ask1(int x, const int y, int Res[2][2], int rL[2], int rR[2])
{
    if (STNum[x] == STNum[y])
        Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STPos[y], Res, rL, rR);
    else
    {
        int tmpL[2], tmpR[2], tmp[2][2];
        Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STSize[STNum[x]], Res, rL, rR);
        x = Father[STTail[STNum[x]]];
        for (; STNum[x] != STNum[y]; x = Father[STTail[STNum[x]]])
        {
            Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STSize[STNum[x]], tmp, tmpL, tmpR);
            CalcL(rL, Res, rL, tmpL);
            CalcR(rR, tmp, rR, tmpR);
            Combine(Res, Res, tmp);
        }
        Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STPos[y], tmp, tmpL, tmpR);
        CalcL(rL, Res, rL, tmpL);
        CalcR(rR, tmp, rR, tmpR);
        Combine(Res, Res, tmp);
    }
}

void Ask2(int x, const int y, int Res[2][2], int rL[2], int rR[2])
{
    if (STNum[x] == STNum[y])
        Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STPos[y]-1, Res, rL, rR);
    else
    {
        int tmpL[2], tmpR[2], tmp[2][2];
        Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STSize[STNum[x]], Res, rL, rR);
        x = Father[STTail[STNum[x]]];
        for (; STNum[x] != STNum[y]; x = Father[STTail[STNum[x]]])
        {
            Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STSize[STNum[x]], tmp, tmpL, tmpR);
            CalcL(rL, Res, rL, tmpL);
            CalcR(rR, tmp, rR, tmpR);
            Combine(Res, Res, tmp);
        }
        if (STPos[y] > STPos[x])
        {
            Query(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], STPos[y]-1, tmp, tmpL, tmpR);
            CalcL(rL, Res, rL, tmpL);
            CalcR(rR, tmp, rR, tmpR);
            Combine(Res, Res, tmp);
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen(InputFileName, "r", stdin);
    freopen(OutputFileName, "w", stdout);
    #endif
    Init();
    Prework();
    char cmd[2];
    for (int x, y, lca, tmp[2][2], Res[2][2], Ans, rL[2], rR[2], tmpL[2], tmpR[2]; m; --m)
    {
        scanf("%s%d", cmd, &x);
        if (cmd[0] == 'C')
        {
            scanf("%s", a[x]);
            Modify(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], x);
        }
        else
        {
            scanf("%d", &y);
            lca = LCA(x, y);
            Ask1(x, lca, Res, rL, rR);
            if (y != lca)
            {
                Ask2(y, lca, tmp, tmpR, tmpL);
                swap(tmp[0][1], tmp[1][0]);
                CalcL(rL, Res, rL, tmpL);
                CalcR(rR, tmp, rR, tmpR);
                Combine(Res, Res, tmp);
            }
            Ans = Max(rL[0], rL[1]);
            printf("%d\n", Ans);
        }
    }
    return 0;
}
来自:计算机科学 / 软件综合
8
已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
ltl 作者
12年11个月前 IP:未同步
299032
希望能对大家有所帮助
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
299348
这几天比以前更冷清了……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
novakon
12年11个月前 IP:未同步
299365
it's like a tutorial teaching people to make headshot kills with HE grenade in CS by learning the working process of HL engine
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
novakon
12年11个月前 IP:未同步
299366
anything more than 10 lines is of no difference to quantum physics in amateur's point of view
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年11个月前 IP:未同步
299602
坛里还是有些OIer的吧……
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
aaaqqqaaa2
12年10个月前 IP:未同步
312216
OIer。。= =
ZJOI是什么?
只听过jsoi~
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论
ltl作者
12年10个月前 IP:未同步
312999
引用第6楼aaaqqqaaa2于2011-08-01 17:16发表的  :
OIer。。= =
ZJOI是什么?
只听过jsoi~

呃……浙江……

您是江苏的?
引用
评论
加载评论中,请稍候...
200字以内,仅用于支线交流,主线讨论请采用回复功能。
折叠评论

想参与大家的讨论?现在就 登录 或者 注册

所属专业
上级专业
同级专业
ltl
学者 笔友
文章
50
回复
3650
学术分
2
2009/09/27注册,1个月20天前活动
暂无简介
主体类型:个人
所属领域:无
认证方式:邮箱
IP归属地:未同步
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

当前账号的附件下载数量限制如下:
时段 个数
{{f.startingTime}}点 - {{f.endTime}}点 {{f.fileCount}}
视频暂不能访问,请登录试试
仅供内部学术交流或培训使用,请先保存到本地。本内容不代表科创观点,未经原作者同意,请勿转载。
音频暂不能访问,请登录试试
支持的图片格式:jpg, jpeg, png
插入公式
评论控制
加载中...
文号:{{pid}}
投诉或举报
加载中...
{{tip}}
请选择违规类型:
{{reason.type}}

空空如也

加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}