1. 题目

BZOJ传送门= ̄ω ̄=

LuoGu传送门= ̄ω ̄=

2. 题解

做了好久呀QvQ

所以记录一下

考虑不带修改点权的树链第K大问题:

  • 首先建主席树(权值线段树),其中root[i]root[fa[i]]为基础上加入点i的点权,这样root[i]所代表的权值线段树表示的是根节点到点i的树链。
  • 对于点a和点b,我们要求它们之间的路径上的第K大点权。设ablcac,则我们在root[a]+root[b]-root[c]-root[fa[c]]中二分就行了,和主席树求区间第K大是一个思路(这里不知道主席树求区间第K大的可以看看这个:【题解】 K-th Number 主席树 POJ – 2104

带修改点权操作也很好搞。

考虑修改点a的权值,把它的权值从x修改到了y

那么以a为根的子树内(包括a)的每个点的主席树都要减去一个x,加上一个y

看到子树,我们不难想到它们在Dfs序上是一段连续区间。

ld[a]为该子树内最小的Dfs序(也就是a的Dfs序),rd[a]为该子树内最大的Dfs序。

那我们要修改的主席树就是区间$[ld[a],rd[a]]$内的那些。。。

这里可以看出是要实现“区间修改,单点查询”。

用树状数组套上主席树即可。

所以我们这样搞:第i个点对应的主席树是第ld[a]棵主席树。

然后修改的时候在树状数组里修改区间$[ld[a],rd[a]]$内的主席树就行了。

好像还要离散化一下。

然后有个小优化,就是对于初始点权,不一定要当做n个修改来搞,可以直接按照无修改操作的那个方式建主席树,时空复杂度$O(nlog_2n)$嘛。然后树状数组套主席树只用来维护修改量。

还有就是对于这题,理论上至少要开$1062\times 80000$个节点的(如果全是修改操作而且每次修改在树状数组中都需要修改$log_2n$个主席树),但是这样空间会爆炸,而且炸得不轻(大概要972MB的内存)。真不知道出题人这样搞想干啥。。。但实测只要开$100\times 80000$个节点就够了(我最后还是开了$175\times 80000$个节点)。如果要究其原因,大概是:

  • 数据随机生成,修改操作较少(估计是$50\%$的操作是修改吧)。
  • 期望上面讲树状数组每次修改大概只有$0.5log_2n$棵主席树被修改。

好吧真是玄学。

代码也很好懂,可以看看。

#include <bits/stdc++.h>

#define NS (80005)
#define LGS (17)
#define lowbit(a) (a&-a)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, t[NS], H[NS << 1], Hs, Q[NS][3];

vector<int> g[NS];

int pre[NS][LGS + 1], dep[NS], ld[NS], rd[NS], dfn;

void Dfs(int a, int fa)
{
    pre[a][0] = fa, dep[a] = dep[fa] + 1, ld[a] = ++dfn;
    for (int i = 1; i <= LGS; i += 1) pre[a][i] = pre[pre[a][i - 1]][i - 1];
    for (int i = 0, tmp; i < g[a].size(); i += 1)
        if (tmp = g[a][i], tmp != fa) Dfs(tmp, a);
    rd[a] = dfn;
}

int lca(int a, int b)
{
    if (dep[a] > dep[b]) swap(a, b);
    for (int i = LGS; i >= 0; i -= 1)
        if (dep[pre[b][i]] >= dep[a]) b = pre[b][i];
    if (a == b) return a;
    for (int i = LGS; i >= 0; i -= 1)
    if (pre[a][i] != pre[b][i])
        a = pre[a][i], b = pre[b][i];
    return pre[a][0];
}

void Make_H()
{
    int top = Hs; sort(H + 1, H + 1 + Hs), H[0] = -1, Hs = 0;
    for (int i = 1; i <= top; i += 1) if (H[i] != H[i - 1]) H[++Hs] = H[i];
}

int Ht(int a)
{
    return lower_bound(H + 1, H + 1 + Hs, a) - H;
}

struct N {int d, l, r;} e[NS * 175];

int sz, rt[NS], dta[NS];

void Update(int pos, int d, int L, int R, int& x)
{
    e[++sz] = e[x], x = sz, e[x].d += d;
    if (L == R) return;
    int Mid = (L + R) >> 1;
    if (pos <= Mid) Update(pos, d, L, Mid, e[x].l);
    else Update(pos, d, Mid + 1, R, e[x].r);
}

void Build(int a)
{
    rt[a] = rt[pre[a][0]], Update(t[a], 1, 1, Hs, rt[a]);
    for (int i = 0, tmp; i < g[a].size(); i += 1)
        if (tmp = g[a][i], tmp != pre[a][0])
            Build(tmp);
}

void add(int x, int pos, int d)
{
    while (x <= n) Update(pos, d, 1, Hs, dta[x]), x += lowbit(x);
}

int Le[NS], Re[NS];

int Query(int k, int L, int R)
{
    if (L == R) return L;
    int Mid = (L + R) >> 1, sum = 0;
    for (int i = 1; i <= Le[0]; i += 1) sum -= e[e[Le[i]].r].d;
    for (int i = 1; i <= Re[0]; i += 1) sum += e[e[Re[i]].r].d;
    if (sum >= k)
    {
        for (int i = 1; i <= Le[0]; i += 1) Le[i] = e[Le[i]].r;
        for (int i = 1; i <= Re[0]; i += 1) Re[i] = e[Re[i]].r;
        return Query(k, Mid + 1, R);
    }
        for (int i = 1; i <= Le[0]; i += 1) Le[i] = e[Le[i]].l;
        for (int i = 1; i <= Re[0]; i += 1) Re[i] = e[Re[i]].l;
        return Query(k - sum, L, Mid);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m);
    for (int i = 1; i <= n; i += 1) IN(t[i]), H[++Hs] = t[i];
    for (int i = 1, a, b; i < n; i += 1)
        IN(a), IN(b), g[a].push_back(b), g[b].push_back(a);
    for (int i = 1; i <= m; i += 1)
    {
        IN(Q[i][0]), IN(Q[i][1]), IN(Q[i][2]);
        if (!Q[i][0]) H[++Hs] = Q[i][2];
    }
    Dfs(1, 0), Make_H();
    for (int i = 1; i <= n; i += 1) t[i] = Ht(t[i]);
    Build(1);
    for (int i = 1, k, a, b, l; i <= m; i += 1)
    {
        k = Q[i][0], a = Q[i][1], b = Q[i][2];
        if (k)
        {
            l = lca(a, b);
            if (dep[a] + dep[b] - dep[l] - dep[l] + 1 < k)
            {
                puts("invalid request!");
                continue;
            }
            Le[0] = Re[0] = 0;
            Re[++Re[0]] = rt[a], Re[++Re[0]] = rt[b];
            Le[++Le[0]] = rt[l], Le[++Le[0]] = rt[pre[l][0]];
            for (int i = ld[a]; i; i -= lowbit(i)) Re[++Re[0]] = dta[i];
            for (int i = ld[b]; i; i -= lowbit(i)) Re[++Re[0]] = dta[i];
            for (int i = ld[l]; i; i -= lowbit(i)) Le[++Le[0]] = dta[i];
            for (int i = ld[pre[l][0]]; i; i -= lowbit(i)) Le[++Le[0]] = dta[i];
            printf("%d\n", H[Query(k, 1, Hs)]);
        }
        else
        {
            add(ld[a], t[a], -1), add(rd[a] + 1, t[a], 1), t[a] = Ht(b);
            add(ld[a], t[a], 1), add(rd[a] + 1, t[a], -1);
        }
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *