Codeforces Round 864 (Div. 2)

A.Li Hua and Maze

算法本质

思维

题目大意

给定n*m的棋盘，点(x1, y1)和(x2, y2)。

请在棋盘上放置方块，阻断(x1, y1)到(x2, y2)的所有路线（不可放起点、终点上）。

输出最小化的方块数。

思路推演

首先想到就是：阻断墙、围绕起点终点围一圈等策略。
随后手动模拟，发现阻断墙这种方式属于“围点”的一种。

所以手动检测起点终点周围的空间是否合法，计算“围点”所需要的代价，然后输出小值。

B.Li Hua and Pattern

算法本质

思维

题目大意

给定n*n的01矩阵、k值。

需要恰好执行k次以下操作，使得矩阵 = 矩阵旋转180°：

• 选择一个方格反转其值

判断是否可行。

思路推演

既然最后矩阵 = 矩阵旋转180°，我们就可以给矩阵的每个格子构建一个对应关系：(x, y) ~ (n-x+1, n-y+1)
我们仅需使得所有格子对都相等即可。

所以我们统计所有的不等格子对数，然后k值减去他们，剩余的k为多余的操作数。（如果不够减，显然不可行）

想要消耗掉剩余的k值，偶数的话显然可行，奇数的话，需要看是否存在自己与自己为一个格子对的情况——即n为奇数。

C.Li Hua and Chess

算法本质

思维

题目大意

给定n*m的棋盘，棋盘中存在一个位置未知的国王，每轮可移动到周围8格之一。

现在你可以进行至多3次询问，每次询问给定一个点(x,y)，返回国王走到(x,y)的最少轮次。（交互题）

最后输出国王位置。

思路推演

3次是一个相对奇怪的数目，但是不管怎样，先手动模拟一下。
模拟了一会，发现这个很类似雷达的检测原理。

第一次询问的显然最优解为(1,1)，最坏的情况是是国王处于一个类L的格子范围中。
然后只需要询问在L的两侧边缘的位置，就可以得到具体位置了。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    //init
    cin>>n>>m;
    int v1, v2, x, y;
    cout<<"? 1 1"<<endl;        // 第一次询问的最优解
    cin>>v1;
    v1++;            

    x = y = v1;        // 初始化x y
    if (v1 <= n)        // 确认y值
    {
        cout<<"? "<<v1<<" 1"<<endl;
        cin>>v2;
        y = v2+1;
    }
    if (v1 <= m)        // 确实x值
    {
        cout<<"? 1 "<<v1<<endl;
        cin>>v2;
        x = v2+1;
    }
    cout<<"! "<<x<<" "<<y<<endl;
    return;
}

D.Li Hua and Tree

算法本质

思维、模拟

题目大意

给定n节点的树、每个节点的节点重要值a[]。

以x节点为根的子树拥有2个属性：树重要值、树大小：

• 树重要值：子树中所有节点的节点重要值之和（含自己）
• 树大小：子树中所有节点个数（含自己）

非叶子节点x有一个属性：最大儿子节点（译为heavy son）：

• 最大儿子节点：其所有儿子节点中，作为子树根节点的树大小最大的 儿子节点（如果有多个值一样的，选下标较小的）

接下来有m次询问or修改，给出op x：

• op==1：询问

  x节点为根的子树的树重要值

• op==2：修改
  设fx是x的父节点，sx是x的最大儿子节点（heavy son）。
  删去fx x边，新增fx sx边——即x边成sx的儿子节点，sx代替x与父节点连接。

思路推演

这种模拟题就是典型的“思路清晰，写的超快”。

我们列出必备的属性：

• 对于节点x来说，其具备的属性：

  • 节点重要值
  • 父节点
  • 最大儿子节点（heavy son）

• 对于x做根节点的子树来说，其具备的属性：

  • 树重要值
  • 树大小

然后根据属性，赋予不同的数据结构、搭配：

• 节点

  • 节点重要值
    不需要修改，直接用a[]表示即可
  • 父节点
    需要修改，用fu[]表示
  • 最大儿子节点（heavy son）
    得搭配“儿子节点集合”使用，需要排序、修改，set显然是个不错的选择，里面放入<树重要值、下标>

• 子树

  • 树重要值
    需要修改，用importance[]表示
  • 树大小
    需要修改，用weight[]表示

对于询问，可以直接输出importance[x]，对于修改，接下来弄清楚其具体的数值转移：（记得画图才清晰可见）
假设当前点x，父节点fx，儿子节点sa sb sc，其中sa为最大儿子节点heavy son。

• 首先可以发现，整个影响范围有限，只关于x fx sa三个节点属性、子树属性
• sa的子树属性完全继承x先前的子树属性（树重要值、树大小）
• x的子树属性需要减去sa先前的子树属性（树重要值、树大小）
• sa的儿子节点集合新增关于x修改后的<树重要值, x>
• x的儿子节点集合删去关于sa的值
• fx的儿子节点集合删去关于先前的x的值，新增当前关于sa的值
• x父节点修改为sa
• sa的父节点修改为fx

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
vector<int> g[maxn];        // 记录题目给出的边，方便初始化图
int weight[maxn], importance[maxn];        // 子树属性
int a[maxn], fu[maxn];        // 节点属性
struct node        
{
    int w, id;
    bool operator < (const node &b) const        // weight较大优先，weight相同id较小优先
    {
        if (w == b.w)    return id < b.id;
        return w > b.w;
    }
};
set<node> son[maxn];        //  <weight, son_id>

void dfs(int u, int fr=0)        // 初始化图
{
    fu[u] = fr;
    for (int v : g[u])
    {
        if (v == fr)    continue;
        dfs(v, u);
        weight[u] += weight[v];
        importance[u] += importance[v];
        son[u].insert({weight[v], v});
    }
    weight[u]++;
    importance[u]+=a[u];
}
void cg(int x)        // 修改函数
{
    if (son[x].size()==0)    return;
    int fx = fu[x];
    node sx=*son[x].begin();        // heavy son

    int new_w_son = weight[x];                // 继承
    int new_i_son = importance[x];            
    int new_w_x = weight[x] - weight[sx.id];            // 减去A树
    int new_i_x = importance[x] - importance[sx.id];
    weight[x] = new_w_x;            // 更新
    importance[x] = new_i_x;
    weight[sx.id] = new_w_son;
    importance[sx.id] = new_i_son;
    son[x].erase(sx);            // 儿子集合更新
    son[sx.id].insert({weight[x], x});
    son[fx].erase({weight[sx.id], x});        
    son[fx].insert({weight[sx.id], sx.id});
    fu[sx.id] = fx;                // 更新父节点
    fu[x] = sx.id;                
}
inline void solve()
{
    //init
    cin>>n>>m;
    rep(i,1,n)    cin>>a[i];
    for (int i=1; i<=n-1; i++)
    {
        int u, v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1);        // 初始化图
    while (m--)    
    {
        int op, x;
        cin>>op>>x;
        if (op==1)    // 输出树重要值
            cout<<importance[x]<<endl;
        else if (op==2)        // 修改
            cg(x);
    }
    return;
}

E.Li Hua and Array

算法本质

思维、数学（欧拉函数）、数据结构（线段树）

题目大意

设f()表示欧拉函数：f(x)表示<=x且与x互质的正整数个数。

现给长度n的a[]、m，接下来会有m次询问、操作：

• op==1：给定l r，操作
  对于i属于[l,r]：a[i] = g(a[i])

• op==2：给定l r，询问

  对于a[l~r]最少需要几次a[i]=f(a[i])才能使得区间内值相等。（这个操作仅本轮）

前置知识

在接下来的思路推演中，默认已知前置知识

• 单个x求欧拉函数复杂度O(sqrt(x))
• 范围欧拉函数有线性筛O(n)的做法。
• 若x为偶数：f(x) = x/2
  若x为基数：f(x) = 小于x的偶数
  这意味x值想要通过不断自我欧拉值更新来抵达1，最多需要2logx次

思路推演

思路清晰

看到操作与查询时，第一时间想到的就是——LCA。同时这是区间点LCA，显然需要用线段树去优化。
再回过头思考一下欧拉函数，其本身的值可以看作一颗节点数为5e6、高度最大为2*log(5e6)的树。（称之为欧拉树）

思路推演-框架建立

接下来根据题意，仔细思考线段树需要的数据、优化（思路清晰）

查询操作应该首先观察

• 先看查询操作：需要log的复杂度搞定区间点的lca，还需要输出到点lca的操作次数

对于两点的lca查询复杂度为2log(5e6)，如果加上维护每个区间的lca值，可以将区间lca值查询复杂度将为：2log(5e6) * log(1e5)。
这个复杂度还可以接受。

• 再看修改操作：也需要log的复杂度搞定，同时还需要维护区间的lca值

对于基础的加法线段树，这一步是采用了懒标记来优化的。但是因为已知需要维护（实时更新）区间的lca值，所以肯定是无法用懒标记维护的。
但是，思考欧拉树的性质，其高度最大为log级别，到根节点后再次操作就无法前进了，所起其实可以暴力更新的。
不过此暴力非彼暴力，这需要一个属性，来表示这个区间的值是否都抵达了根节点，若都抵达了，则在更新中忽略这个区间。
这样操作，单次修改的均摊复杂度为：2log(5e6) * log(1e5)。

再加上区间lca的值、点到lca值的操作次数。

到此为止，代码的框架已出：

• 构建2颗树：欧拉树、线段树

线段树节点属性：

• 基础的l r
• 布尔值f：标记区间是否全部值为欧拉树根节点
• zu：区间所有元素的lca节点
• cnt：区间所有元素到zu的操作数

思路推演-细节补充

接下来需要补充方法。

欧拉树，只是名义上的树而已，实际不用建树，把线性欧拉函数的板子添加到代码中。

然后构建树节点node：

// l r为节点基础属性
// zu记录区间lca值，cnt记录区间元素都抵达zu需要的操作数
// f记录区间元素是否都抵达了根节点（优化更新指令）
struct node
{
    int l, r, zu, cnt, f;        
};
node tr[maxn*4];

随后建树，但是建树的过程发现，我们还没有写区间和区间结合的函数。
正好这部分修改、询问操作都需要，就单独写成一个函数：

• zu：需要暴力求解
• cnt：通过zu整体计算
• f：直接判断即可

因为是线段树中的区间结合函数，所以可以看作是其大区间的更新函数：

void update(node &fu, node &lson, node &rson)        // fu区间的属性，通过lson和rson来更新
{
    fu.l = lson.l;        // 初始化l,r
    fu.r = rson.r;
    fu.f = lson.f && rson.f;        // 更新f
    fu.cnt = lson.cnt + rson.cnt;    // 初始化cnt

    int x=lson.zu, y=rson.zu;        // x,y为区间左右两端的lca值
    while (x!=y)    // 暴力寻找lca值
    {
        if (x>y)    x=phi[x], fu.cnt+=(lson.r-lson.l+1);    // 更新cnt
        else        y=phi[y], fu.cnt+=(rson.r-rson.l+1);
    }
    fu.zu = x;        // 更新zu
}

然后我们再写建树函数：

void build(int u, int l, int r)
{
    tr[u].l = l;
    tr[u].r = r;
    if(l == r)        // 结束递归语句
    {
        tr[u].zu = a[l];        // 单个点构成的区间，其lca值就是自己
        tr[u].cnt = 0;        // 自己到祖先的距离为0
        tr[u].f = a[l]==1;    // 检查所有元素是否为根节点值1    
        return;
    }
    int mid = (l + r)/2;
    build(2*u, l, mid), build(2*u+1, mid+1, r);
    update(tr[u], tr[2*u], tr[2*u+1]);        // 更新区间属性
}

接着需要修改函数：

void modify(int u, int l, int r)
{
    if (tr[u].f)    return;    // 优化，如果区间元素都抵达了根节点，就不用更新了

    if (tr[u].l==tr[u].r)    // 单值区间
    {
        tr[u].zu = phi[tr[u].zu];    // 更新lca值（cnt值一直为0不需要改变）
        tr[u].f = tr[u].zu==1;        // 检查是否抵达根节点
        return;
    }

    int mid=(tr[u].l+tr[u].r)/2;
    if (l<=mid)        modify(2*u, l, r);        // 递归左子树
    if (r>mid)        modify(2*u+1, l, r);    // 递归右子树
    update(tr[u], tr[2*u], tr[2*u+1]);        // 更新区间属性
}

再然后是查询函数：
查询函数的细节略有不同，核心在于根据需要构建一个新的node，所以用node最为返回值显然更好

node query(int u, int l, int r)
{
    if (l<=tr[u].l && tr[u].r<=r)    return tr[u];    // 区间完全覆盖，返回这个区间

    int mid=(tr[u].l+tr[u].r)/2;
    if (r<=mid)        return query(2*u, l, r);        // 仅在左半边，交给左节点处理
    if (l>mid)        return query(2*u+1, l, r);        // 仅在右半边，交给右节点处理
    node res, lson=query(2*u, l, r), rson=query(2*u+1, l, r);    // 左右节点都有用，分别处理
    update(res, lson, rson);        // 更新区间属性
    return res;
}

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
const int maxn=1e5+5;        // 如果都开5e6且开longlong会报内存
const int maxm=5e6+5;
    
int a[maxn];        // 初始的欧拉值
vector<int> prime;
bool not_prime[maxm];
int phi[maxm];        // phi[x] = x的欧拉函数值
void get_phi(int max_num)
{
    phi[1]=1;
    for(int i=2; i<=max_num; i++)        // 同时i也是枚举的倍数
    {
        if(!not_prime[i])        // i是质数
        {
            prime.push_back(i);        // 记录质数
            phi[i] = i-1;            // phi[]对素数的专程处理
        }
        for(int idx=0; prime[idx]*i<=max_num; idx++)
        {
            not_prime[i*prime[idx]] = 1;            // i*primes[j]不是质数
            if(i%prime[idx]==0)        // 情况1 primes[j]是i的最小质因子
            {
                phi[i*prime[idx]] = phi[i]*prime[idx];
                break;
            }
            phi[i*prime[idx]] = phi[i]*(prime[idx]-1);    //情况2
        }
    }
}

// l r为节点基础属性
// zu记录区间lca值，cnt记录区间元素都抵达zu需要的操作数
// f记录区间元素是否都抵达了根节点（优化更新指令）
struct node
{
    int l, r, zu, cnt, f;        
};
node tr[maxn*4];

void update(node &fu, node &lson, node &rson)        // fu区间的属性，通过lson和rson来更新
{
    fu.l = lson.l;        // 初始化l,r
    fu.r = rson.r;
    fu.f = lson.f && rson.f;        // 更新f
    fu.cnt = lson.cnt + rson.cnt;    // 初始化cnt

    int x=lson.zu, y=rson.zu;        // x,y为区间左右两端的lca值
    while (x!=y)    // 暴力寻找lca值
    {
        if (x>y)    x=phi[x], fu.cnt+=(lson.r-lson.l+1);    // 更新cnt
        else        y=phi[y], fu.cnt+=(rson.r-rson.l+1);
    }
    fu.zu = x;        // 更新zu
}

void build(int u, int l, int r)
{
    tr[u].l = l;
    tr[u].r = r;
    if(l == r)        // 结束递归语句
    {
        tr[u].zu = a[l];        // 单个点构成的区间，其lca值就是自己
        tr[u].cnt = 0;        // 自己到祖先的距离为0
        tr[u].f = a[l]==1;    // 检查所有元素是否为根节点值1    
        return;
    }
    int mid = (l + r)/2;
    build(2*u, l, mid), build(2*u+1, mid+1, r);
    update(tr[u], tr[2*u], tr[2*u+1]);        // 更新区间属性
}

void modify(int u, int l, int r)
{
    if (tr[u].f)    return;    // 优化，如果区间元素都抵达了根节点，就不用更新了

    if (tr[u].l==tr[u].r)    // 单值区间
    {
        tr[u].zu = phi[tr[u].zu];    // 更新lca值（cnt值一直为0不需要改变）
        tr[u].f = tr[u].zu==1;        // 检查是否抵达根节点
        return;
    }

    int mid=(tr[u].l+tr[u].r)/2;
    if (l<=mid)        modify(2*u, l, r);        // 递归左子树
    if (r>mid)        modify(2*u+1, l, r);    // 递归右子树
    update(tr[u], tr[2*u], tr[2*u+1]);        // 更新区间属性
}

node query(int u, int l, int r)
{
    if (l<=tr[u].l && tr[u].r<=r)    return tr[u];    // 区间完全覆盖，返回这个区间

    int mid=(tr[u].l+tr[u].r)/2;
    if (r<=mid)        return query(2*u, l, r);        // 仅在左半边，交给左节点处理
    if (l>mid)        return query(2*u+1, l, r);        // 仅在右半边，交给右节点处理
    node res, lson=query(2*u, l, r), rson=query(2*u+1, l, r);    // 左右节点都有用，分别处理
    update(res, lson, rson);        // 更新区间属性
    return res;
}

inline void solve()
{
    //init
    get_phi(5e6);        // 线性筛欧拉值
    cin>>n>>m;
    rep(i,1,n)    cin>>a[i];
    build(1, 1, n);        // 建树

    while (m--)
    {
        int op, l, r;
        cin>>op>>l>>r;
        if (op==1)        // 修改操作
            modify(1, l, r);
        else        // 询问操作
            cout<<query(1, l, r).cnt<<endl;
    }
    
    return;
}