15年7个月前IP:未同步
296701
14楼
为一下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:44最后登录 2024/09/22 17:57:51
主体类型:个人
所属领域:无
认证方式:邮箱
IP归属地:0

个人简介

暂未填写
笔记
{{note.content}}
{{n.user.username}}
{{fromNow(n.toc)}} {{n.status === noteStatus.disabled ? "已屏蔽" : ""}} {{n.status === noteStatus.unknown ? "正在审核" : ""}} {{n.status === noteStatus.deleted ? '已删除' : ''}}
  • 编辑
  • 删除
  • {{n.status === 'disabled' ? "解除屏蔽" : "屏蔽" }}
我也是有底线的