欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

[Luogu P4338] [BZOJ 5212] [ZJOI 2018] 历史

程序员文章站 2022-07-13 11:57:39
...

洛谷传送门

BZOJ传送门

题目背景

九条可怜是一个热爱阅读的女孩子。

题目描述

这个世界有 n 个城市,这 n 个城市被恰好 n1 条双向道路联通,即任意两个城市都可以 互相到达。同时城市 1 坐落在世界的中心,占领了这个城市就称霸了这个世界。

在最开始,这 n 个城市都不在任何国家的控制之下,但是随着社会的发展,一些城市会崛 起形成国家并夺取世界的霸权。为了方便,我们标记第 i 个城市崛起产生的国家为第 i 个国家。 在第 i 个城市崛起的过程中,第 i 个国家会取得城市 i 到城市 1 路径上所有城市的控制权。

新的城市的崛起往往意味着战争与死亡,若第 i 个国家在崛起中,需要取得一个原本被国 家 j(ji) 控制的城市的控制权,那么国家 i 就必须向国家 j 宣战并进行战争。

现在,可怜知道了,在历史上,第 i 个城市一共崛起了 ai 次。但是这些事件发生的相对顺 序已经无从考究了,唯一的信息是,在一个城市崛起称霸世界之前,新的城市是不会崛起的。

战争对人民来说是灾难性的。可怜定义一次崛起的灾难度为崛起的过程中会和多少不同的国家进行战争(和同一个国家进行多次战争只会被计入一次)。可怜想要知道,在所有可能的崛 起顺序中,灾难度之和最大是多少。

同时,在考古学家的努力下,越来越多的历史资料被发掘了出来,根据这些新的资料,可怜会对 ai 进行一些修正。具体来说,可怜会对 ai 进行一些操作,每次会将 ax 加上 w。她希望 在每次修改之后,都能计算得到最大的灾难度。

然而可怜对复杂的计算并不感兴趣,因此她想让你来帮她计算一下这些数值。 对题面的一些补充:

  • 同一个城市多次崛起形成的国家是同一个国家,这意味着同一个城市连续崛起两次是不会 和任何国家开战的:因为这些城市原来就在它的控制之下。
  • 在历史的演变过程中,第 i 个国家可能会有一段时间没有任何城市的控制权。但是这并不 意味着第 i 个国家灭亡了,在城市 i 崛起的时候,第 i 个国家仍然会取得 1i 路径上的城市的控制权。

输入输出格式

输入格式:

第一行输入两个整数 n,m 表示城市个数和操作个数。

第二行输入 n 个整数表示 ai 的初始值。 接下来 n1 行,每行输入两个整数 ui,vi(1ui,vin)描述了一条道路。

接下来 m 行每行输入两个整数 xi,wi 表示将 axi 加上 wi

输出格式:

输出共 m+1 行,第一行表示初始的 ai 的答案,接下来 m 行每行表示这次修正后的答案。

输入输出样例

输入样例#1:
5 3 
1 1 1 1 1 
1 2 
1 3 
2 4 
2 5 
2 1 
3 1
4 1
输出样例#1:
6 
7 
9
10

说明

在修正开始之前,如果按照所在城市 4,1,5,3,2 的顺序崛起,那么依次会和 0,1,2,1,2 个 国家进行战争。

这时一共会产生 6 对敌对关系。可以证明这是所有崛起顺序中的最大值。

[Luogu P4338] [BZOJ 5212] [ZJOI 2018] 历史

解题分析

蒟蒻只会10分全排列暴力滚粗QAQ…

[Luogu P4338] [BZOJ 5212] [ZJOI 2018] 历史

题目翻译:给定一棵树中每个点access的次数, 最大化access时经过的不同splay的次数。

这是啥?似乎和LCT有点关系?似乎没什么思路啊

我们还是先考虑没有修改的情况。为了得到最大的切换数, 我们先考虑得到一个点的最大切换数。

容易发现似乎对于某个点, 它的子树中的access顺序对于这个点的切换数是没有影响的(只要从不同点出发即可), 所以子树中的顺序对当前层的答案是没有影响的。 同时, 为了最大化切换数, 我们肯定要连续access不同子树中的节点(如果access同一子树中的节点只会每次带来1的切换数, 但如果access不同子树中的节点就会在子树内留一部分, 在之后同一子树中access时带来更大收益。或者说, 同一子树中access时的收益其实是算在access时那个点上的,并没有带来更多的收益)。设节点i 的贡献为val[i],在i节点子树内(包括节点i本身)的access次数和为tot[i],子树内access次数最大的子树或当前点的次数为mx[i]。整理一下, 我们可以得出以下贡献计算方程:

val[i]=min(tot[i]1, 2×(tot[i]mx[i]))

Ans=i=1nval[i]

min的原因是如果某个子树/当前点i过大, 有一部分的access将会浪费(不得不重复在一棵子树内access)。具体而言,当2×mx[i]tot[i]+1时, 将会产生这种情况。在这里我们不妨称这种情况为重子树。

那么现在我们就可以O(N)应付不带询问的情况了,30分到手QAQ…

现在我们考虑如何带修改。

我们发现, 如果一个节点的一棵子树中的点被修改(只会增加次数), 而这棵子树的大小恰好满足siz[i]×2tot[i]+1, 那么对于这个节点其对答案的贡献是没有改变的。进而我们想到, 向上更新子树大小的过程就像LCT中的access过程, 又因为对于每一个节点, 其最多有一个重子树,所以我们可以跳过一个连续的重子树连成的链, 考虑在重子树与非重子树连接处更新答案。进而我们想到, 似乎可以将当前节点和重子树节点间连为实边, 其它边连为虚边, 用LCT维护即可。 为了方便查询子树信息, 我们可以将重子树节点统一连到右儿子上,查询子树信息只需splay再查询并合并右儿子和当前节点的信息即可。

这样做修改时一路爬树, 均摊总复杂度为O(Nlog(N))

说起来简单, 实现起来有很多细节, 像博主这种蒟蒻肯定是打不出来的qwq

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#define R register
#define IN inline
#define gc getchar()
#define W while
#define MX 500050
#define ls tree[now].son[0]
#define rs tree[now].son[1]
#define ll long long
#define dad tree[now].fat
template <class T>
IN void in(T &x)
{
    x = 0; R char c = gc;
    W (!isdigit(c)) c = gc;
    W (isdigit(c))
    x = (x << 1) + (x << 3) + c - 48, c = gc;
}
int head[MX];
int dot, q, cnt;
ll ans;
struct Edge
{
    int to, nex;
}edge[MX << 1];
IN void addedge(const int &from, const int &to)
{
    edge[++cnt] = {to, head[from]};
    head[from] = cnt;
}
struct Node
{
    int son[2], fat;
    ll sum, vir, val;
}tree[MX];
namespace LCT
{
    IN bool get(const int &now) {return tree[dad].son[1] == now;}
    IN bool nroot(const int &now) {return tree[dad].son[1] == now || tree[dad].son[0] == now;}
    IN void pushup(const int &now) {tree[now].sum = tree[now].val + tree[now].vir + tree[ls].sum + tree[rs].sum;}
    IN void rotate(const int &now)
    {
        R bool dir = get(now);
        R int fa = dad, grand = tree[fa].fat;
        tree[fa].son[dir] = tree[now].son[dir ^ 1];
        tree[tree[now].son[dir ^ 1]].fat = fa;
        if(nroot(fa)) tree[grand].son[get(fa)] = now;
        tree[now].fat = grand;
        tree[fa].fat = now;
        tree[now].son[dir ^ 1] = fa;
        pushup(fa);
    } 
    IN void splay(R int now)
    {
        R int fa, grand;
        W (nroot(now))
        {
            fa = dad, grand = tree[fa].fat;
            if(nroot(fa)) rotate(get(now) == get(fa) ? fa : now);
            rotate(now);
        }
        pushup(now);
    }
    IN void access(R int now, R int pre, const ll &del)//和下面类似
    {
        ll sum;
        for (; now; pre = now, now = dad)
        {
            splay(now);
            sum = tree[now].val + tree[now].vir + tree[rs].sum;
            if(rs) ans -= (sum - tree[rs].sum) << 1ll;
            else if((tree[now].val << 1ll) >= sum + 1) ans -= (sum - tree[now].val) << 1ll;
            else ans -= sum - 1;

            sum += del; tree[now].sum += del; tree[now].vir += del;
            if(sum + 1 > (tree[rs].sum << 1ll)) tree[now].vir += tree[rs].sum, rs = 0;
            if(sum + 1 <= tree[pre].sum << 1ll) rs = pre, tree[now].vir -= tree[rs].sum;
            //下面的子树变成了自己的右儿子, 连成重子树

            if(rs) ans += (sum - tree[rs].sum) << 1ll;
            else if(sum + 1 <= (tree[now].val << 1ll)) ans += (sum - tree[now].val) << 1ll;
            else ans += sum - 1;
        }
    }
    IN void modify(R int now, const ll &del)
    {
        ll sum;
        splay(now);
        //清除当前点与其儿子节点的贡献
        sum = tree[now].val + tree[now].vir + tree[rs].sum;//当前子树信息
        if(rs) ans -= (sum - tree[rs].sum) << 1ll;//有右儿子说明在重子树的链上, 在下面的①中讨论
        else if((tree[now].val << 1ll) >= sum + 1) ans -= (sum - tree[now].val) << 1ll;
        //本来自己就很重, 是重链的末尾。
        else ans -= sum - 1;//不是重子树链上的任意一个点

        sum += del; tree[now].sum += del; tree[now].val += del;//更新树上信息
        if(sum + 1 > (tree[rs].sum << 1ll)) tree[now].vir += tree[rs].sum, rs = 0;
        //这棵树变得更平衡了, 失去了重子树, 将右儿子的信息归在当前点的虚子树信息里

        if(rs) ans += (sum - tree[rs].sum) << 1ll;//如果仍有重子树, 加回去
        else if(sum + 1 <= (tree[now].val << 1ll)) ans += (sum - tree[now].val) << 1ll;
        //自己变重了, 加上作为重子树的贡献
        else ans += sum - 1;//仍然没有重子树
        access(dad, now, del);//向上更新
    }
}
void dp(const int &now)//树上dp预处理
{
    tree[now].sum = tree[now].val;
    ll mx = tree[now].val, id = now;
    for (R int i = head[now]; i; i = edge[i].nex)
    {
        if(edge[i].to == dad) continue;
        tree[edge[i].to].fat = now;
        dp(edge[i].to); tree[now].vir += tree[edge[i].to].sum, tree[now].sum += tree[edge[i].to].sum;
        if(tree[edge[i].to].sum > mx) mx = tree[id = edge[i].to].sum;
    }
    if((mx << 1ll) < tree[now].sum + 1) ans += tree[now].sum - 1;
    else ans += (tree[now].sum - mx) << 1ll;
    if(id != now && (mx << 1ll) >= tree[now].sum + 1) rs = id;//统一连成右儿子
    tree[now].vir = tree[now].sum - tree[now].val - tree[rs].sum;
}
int main(void)
{
    int a, b;
    in(dot), in(q);
    for (R int i = 1; i <= dot; ++i) in(tree[i].val);
    for (R int i = 1; i < dot; ++i)
    in(a), in(b), addedge(a, b), addedge(b, a);
    dp(1); printf("%lld\n", ans);
    W (q--) in(a), in(b), LCT::modify(a, b), printf("%lld\n", ans);
}

附:

①:对于一段重子树形成的链, 情况如下:

[Luogu P4338] [BZOJ 5212] [ZJOI 2018] 历史

如果我们断开BC之间的边, 答案的减少值Δ=val[B]=(siz[B]siz[C])2,而显然这个改变不会对AB造成影响。