已屏蔽 原因:{{ notice.reason }}已屏蔽
{{notice.noticeContent}}
~~空空如也
为一下LZ是什么专业的?为什么学C++?难道是搞信息的?表示对现在大学教的内容不解,求LZ介绍
顺便贴个小程序,一道题目,前一段写的(ZJOI《树的统计》 - 树链剖分)
/*
Title: count
Data: 2011-1-30
*/

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

#define InputFileName        "XXXXXXXX"
#define OutputFileName        "count.out"

using namespace std;

const int MaxN = 31000, oo = 0x7FFFFFFF;

bool View[MaxN];
int n, m, u[MaxN*2], v[MaxN*2], Next[MaxN*2], Head[MaxN], w[MaxN], Size[MaxN], ENum, Heavy[MaxN], Depth[MaxN], d[MaxN*2][20], Pos[MaxN], Total, Line[MaxN], Father[MaxN];
int Left[MaxN*4], Right[MaxN*4], Sum[MaxN*4], MaxNum[MaxN*4], STNum[MaxN], STSize[MaxN], STTotal, Root[MaxN], STPos[MaxN], S[MaxN], T[MaxN];

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

void Init()
{
    scanf("%d", &n);
    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("%d", w+i);
    scanf("%d", &m);
}

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[Father[v[i]] = t]+1;
            DFS(v[i]);
            d[++Total][0] = t;
            Size[t] += Size[v[i]];
            if (! Heavy[t] || Size[Heavy[t]] < Size[v[i]])
                Heavy[t] = v[i];
        }
}

inline int Max(const int x, const int y)
{
    return x > y ? x : y;
}

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

void RMQInitialize()
{
    for (int i, j = 1, k = (int)(log2(Total)+1E-8), l; j <= k; ++j)
        for (i = 1, l = 1 << j; i+l-1 <= Total; ++i)
            d[i][j] = RMQMin(d[i][j-1], d[i+(l >> 1)][j-1]);
}

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

void NewTree(const int t, const int l, const int r)
{
    if (l == r)
    {
        Sum[t] = MaxNum[t] = w[Line[l]];
        return;
    }
    const int mid = l+r >> 1;
    NewTree(Left[t] = ++STTotal, l, mid);
    NewTree(Right[t] = ++STTotal, mid+1, r);
    Sum[t] = Sum[Left[t]]+Sum[Right[t]];
    MaxNum[t] = Max(MaxNum[Left[t]], MaxNum[Right[t]]);
}

void Build()
{
    memset(View, 0, sizeof(View));
    Total = 0;
    for (int k = 1, i, j; k < 2*n; ++k)
        if (! View[i = d[k][0]])
        {
            for (View[Line[STPos[i] = STSize[++Total] = 1] = j = i] = 1; Heavy[j]; View[Line[STPos[Heavy[j]] = ++STSize[Total]] = j = Heavy[j]] = 1);
            S[Total] = i;
            T[Total] = j;
            for (STNum[j = i] = Total; Heavy[j]; STNum[j = Heavy[j]] = Total);
            NewTree(Root[Total] = ++STTotal, 1, STSize[Total]);
        }
}

void Modify(const int t, const int l, const int r, const int p, const int k)
{
    if (l == r)
    {
        Sum[t] = MaxNum[t] = k;
        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);
    Sum[t] = Sum[Left[t]]+Sum[Right[t]];
    MaxNum[t] = Max(MaxNum[Left[t]], MaxNum[Right[t]]);
}

int STSum(const int t, const int l, const int r, const int x, const int y)
{
    if (x <= l && y >= r)
        return Sum[t];
    int mid = l+r >> 1, Res = 0;
    if (x <= mid)
        Res = STSum(Left[t], l, mid, x, y);
    if (y > mid)
        Res += STSum(Right[t], mid+1, r, x, y);
    return Res;
}

int STMax(const int t, const int l, const int r, const int x, const int y)
{
    if (x <= l && y >= r)
        return MaxNum[t];
    int mid = l+r >> 1, Res = -oo;
    if (x <= mid)
        Res = STMax(Left[t], l, mid, x, y);
    if (y > mid)
        Res = Max(Res, STMax(Right[t], mid+1, r, x, y));
    return Res;
}

inline int GetSum(const int x, int y)
{
    int Res = 0;
    for (; Depth[x] < Depth[S[STNum[y]]]; y = Father[S[STNum[y]]])
        Res += STSum(Root[STNum[y]], 1, STSize[STNum[y]], 1, STPos[y]);
    Res += STSum(Root[STNum[y]], 1, STSize[STNum[y]], STPos[x], STPos[y]);
    return Res;
}

inline int GetMax(const int x, int y)
{
    int Res = -oo;
    for (; Depth[x] < Depth[S[STNum[y]]]; y = Father[S[STNum[y]]])
        Res = Max(Res, STMax(Root[STNum[y]], 1, STSize[STNum[y]], 1, STPos[y]));
    Res = Max(Res, STMax(Root[STNum[y]], 1, STSize[STNum[y]], STPos[x], STPos[y]));
    return Res;
}

int main()
{
    #ifndef ONLINE_JUDGE
    freopen(InputFileName, "r", stdin);
    freopen(OutputFileName, "w", stdout);
    #endif
    Init();
    memset(View, 0, sizeof(View));
    Depth[1] = 1;
    DFS(1);
    RMQInitialize();
    Build();
    char cmd[10];
    int x, y, LCA, Ans, sx, sy;
    for (; m; --m)
    {
        scanf("%s%d%d", cmd, &x, &y);
        if (cmd[0] == 'C')
            Modify(Root[STNum[x]], 1, STSize[STNum[x]], STPos[x], w[x] = y);
        else
        {
            LCA = RMQ(x, y);
            if (cmd[1] == 'M')
                Ans = Max(GetMax(LCA, x), GetMax(LCA, y));
            else
                Ans = GetSum(LCA, x)+GetSum(LCA, y)-w[LCA];
            printf("%d\\n", Ans);
        }
    }
    return 0;
}
文号 / 296701

千古风流
名片发私信
学术分 2
总主题 50 帖总回复 3652 楼拥有证书:学者 笔友
注册于 2009-09-27 17:05最后登录 2024-02-08 12:35
主体类型:个人
所属领域:无
认证方式:邮箱
IP归属地:未同步

个人简介

暂未填写
文件下载
加载中...
{{errorInfo}}
{{downloadWarning}}
你在 {{downloadTime}} 下载过当前文件。
文件名称:{{resource.defaultFile.name}}
下载次数:{{resource.hits}}
上传用户:{{uploader.username}}
所需积分:{{costScores}},{{holdScores}}下载当前附件免费{{description}}
积分不足,去充值
文件已丢失

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

空空如也

插入资源
全部
图片
视频
音频
附件
全部
未使用
已使用
正在上传
空空如也~
上传中..{{f.progress}}%
处理中..
上传失败,点击重试
等待中...
{{f.name}}
空空如也~
(视频){{r.oname}}
{{selectedResourcesId.indexOf(r.rid) + 1}}
处理中..
处理失败
插入表情
我的表情
共享表情
Emoji
上传
注意事项
最大尺寸100px,超过会被压缩。为保证效果,建议上传前自行处理。
建议上传自己DIY的表情,严禁上传侵权内容。
点击重试等待上传{{s.progress}}%处理中...已上传,正在处理中
空空如也~
处理中...
处理失败
加载中...
草稿箱
加载中...
此处只插入正文,如果要使用草稿中的其余内容,请点击继续创作。
{{fromNow(d.toc)}}
{{getDraftInfo(d)}}
标题:{{d.t}}
内容:{{d.c}}
继续创作
删除插入插入
插入公式
评论控制
加载中...
文号:{{pid}}
加载中...
详情
详情
推送到专栏从专栏移除
设为匿名取消匿名
查看作者
回复
只看作者
加入收藏取消收藏
收藏
取消收藏
折叠回复
置顶取消置顶
评学术分
鼓励
设为精选取消精选
管理提醒
编辑
通过审核
评论控制
退修或删除
历史版本
违规记录
投诉或举报
加入黑名单移除黑名单
查看IP
{{format('YYYY/MM/DD HH:mm:ss', toc)}}
ID: {{user.uid}}