首页 > 其他分享 >【题解】CF893F Subtree Minimum Query

【题解】CF893F Subtree Minimum Query

时间:2023-01-13 11:44:33浏览次数:48  
标签:sz CF893F val int 题解 mid dfs Minimum maxn

那个……令姐……能以成亲为前提……和我交往吗(娇羞)

集训完刚好开方舟春活,并且我刚好攒够了给令姐买衣服的石头,这真的是巧合吗?

思路

各种做法,但是有强化版。

首先是 naive 的线段树合并维护深度做法。

然后可以考虑主席树。正常来说距离不超过 \(k\) 的子树问题,是以 dfs 序为时间轴,以深度为下标建主席树。

但是取最小值不具有可减性,所以以深度为时间轴,以 dfs 序为下标建主席树,这样只需要在某个版本的主席上查询一段连续区间的最小值即可。

当然还有诡异的树套树做法,但是我不是很懂,有懂哥可以教一下。


强化版 BZOJ#4771:维护子树内不同颜色的出现次数。

这里有一个虚树差分 + 主席树的 \(O(n \log n)\) 做法。

树链的并:对于 \(k\) 个树上的不同结点 \(a_1, ..., a_n\),

考虑覆盖根到每一个结点的路径。那么可以先把 \(a\) 按照 dfs 序排序,然后将 \(a_i\) 到 \(\operatorname{lca}(a_i, a_{i + 1})\) 之间的路径加一。

虚树差分:对于树链的并中每个结点权值加一。

考虑对 \(a\) 建立出虚树,然后考虑将虚树上每个点的权值赋为 \(1\),按 dfs 序排序后将 \(\operatorname{lca}(a_i, a_{i + 1})\) 的点权减一,最后查询子树和。


回到原题。对于每种颜色的结点,贡献实际上就是一个树链并。

考虑用虚树差分维护。用类似弱化版的主席树维护一下深度。

这里每种颜色的贡献是动态的,不能直接虚树差分。可以用一个 set 维护单种颜色的结点中 dfs 序的前驱后继,这样就可以动态维护了。

代码懒得写了,网上一搜都是。

代码

#include <cstdio>
#include <vector>
using namespace std;

const int maxn = 1e5 + 5;
const int t_sz = maxn * 40;
const int inf = 0x3f3f3f3f;

inline int min(const int &a, const int &b) { return (a <= b ? a : b); }

inline int read()
{
    int res = 0;
    char ch = getchar();
    while ((ch < '0') || (ch > '9')) ch = getchar();
    while ((ch >= '0') && (ch <= '9'))
    {
        res = res * 10 + ch - '0';
        ch = getchar();
    }
    return res;
}

inline void write(int x)
{
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

namespace PST
{
    int cnt = 0;
    int ls[t_sz], rs[t_sz], val[t_sz];

    inline void push_up(int k) { val[k] = min(val[ls[k]], val[rs[k]]); }

    inline int build(int l, int r)
    {
        int k = ++cnt;
        val[k] = inf;
        if (l == r) return k;
        int mid = (l + r) >> 1;
        ls[k] = build(l, mid);
        rs[k] = build(mid + 1, r);
        return k;
    }

    inline int update(int pre, int l, int r, int p, int w)
    {
        int k = ++cnt;
        ls[k] = ls[pre], rs[k] = rs[pre], val[k] = min(val[pre], w);
        if (l == r) return k;
        int mid = (l + r) >> 1;
        if (p <= mid) ls[k] = update(ls[pre], l, mid, p, w);
        else rs[k] = update(rs[pre], mid + 1, r, p, w);
        return k;
    }

    inline int query(int k, int l, int r, int ql, int qr)
    {
        if ((l >= ql) && (r <= qr)) return val[k];
        int mid = (l + r) >> 1, res = inf;
        if (ql <= mid) res = min(res, query(ls[k], l, mid, ql, qr));
        if (qr > mid) res = min(res, query(rs[k], mid + 1, r, ql, qr));
        return res;
    }
}

struct item
{
    int p, w;
} ;

int n, m, root, cnt;
int dep[maxn], dfn[maxn], w[maxn], rt[maxn], sz[maxn];
vector<int> g[maxn];
vector<item> nd[maxn];

void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    dfn[u] = ++cnt;
    sz[u] = 1;
    for (int v : g[u])
    {
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int main()
{
    int last_ans = 0;
    n = read(), root = read();
    for (int i = 1; i <= n; i++) w[i] = read();
    for (int i = 1, u, v; i <= n - 1; i++)
    {
        u = read(), v = read();
        g[u].push_back(v), g[v].push_back(u);
    }
    dfs(root, 0);
    for (int i = 1; i <= n; i++) nd[dep[i]].push_back((item){dfn[i], w[i]});
    rt[0] = PST::build(1, n);
    for (int i = 1; i <= n; i++)
    {
        rt[i] = rt[i - 1];
        for (item it : nd[i]) rt[i] = PST::update(rt[i], 1, n, it.p, it.w);
    }
    m = read();
    while (m--)
    {
        int x, k;
        x = read(), k = read();
        x = (x + last_ans) % n + 1, k = (k + last_ans) % n;
        write(last_ans = PST::query(rt[min(dep[x] + k, n)], 1, n, dfn[x], dfn[x] + sz[x] - 1));
        putchar('\n');
    }
    return 0;
}

标签:sz,CF893F,val,int,题解,mid,dfs,Minimum,maxn
From: https://www.cnblogs.com/lingspace/p/cf893f.html

相关文章

  • 题解 P8294 [省选联考 2022] 最大权独立集问题
    Solution根据一些逝去的记忆可以得到一个DP状态:\(f_{u,x,y}\)表示\(u\)这棵子树,\(x\)从子树出去,\(y\)进来这棵子树。然后讨论一下状态转移,可以暴力枚举状态,暴力枚......
  • CF244A Dividing Orange 题解
    Description有\(n\timesk\)个橘子,\(k\)个小朋友每人拿\(n\)个,但是每个人都指定了一个橘子\(a_i\),分配时必须要把\(a_i\)给第\(i\)个小朋友,求任一分配方案。So......
  • js加法精度问题解决
    //加法exportconstnumAdd=(num1,num2)=>{letbaseNum,baseNum1,baseNum2try{baseNum1=num1.toString().split('.')[1].length}cat......
  • maven引入本地jar不能打入部署包的问题解决
    引入的三方依赖 jar 包, scope 为 system 的包 maven 默认是不打包进去的,需要加这个配置在pom.xml文件中找到spring-boot-maven-plugin插件,添加如下配置<configu......
  • 【题解】P4126 [AHOI2009]最小割
    题意求最小割和可行边和必须边。思路清真,清真,还是**的清真。考虑可行边的充要条件:满流不存在另一条\(u,v\)间的最短路,即在残量网络上不存在包含\(u,v\)......
  • 【题解】P6071 『MdOI R1』Treequery
    海浪尽头的你啊,到底何时归来?额滴就木异象啊……思路清真树论。树论地考虑祖先后代关系,分讨一下。用ST表处理一下\(lca(l,r)=u\):\(u,p\)无祖先后代关系,答案......
  • 洛谷P7792 KRIZA 题解 C++
    洛谷P7792KRIZA题解C++题目概述:题目传送门Sisyphus在一个圆形的房间里,房间内有n扇锁着的门,他有n把钥匙,其中第i把钥匙对应第$v_i$扇门,遇到不匹配的钥匙就放......
  • 【题解】P4899 [IOI2018] werewolf 狼人
    そうやってただ日が暮れるまで語り掛ける本当の言葉题意给定一个有向图和若干询问,每次询问是否存在一条满足条件的路径:端点分别为\(u,v\)前面一段不经过\([1,L......
  • 传递游戏【题解】
    Description毛大神最近在玩一个传递游戏,即有\(N\)个人在做传递物品的游戏,这N个人的编号为\(1,2,3,...,N-1,N\)。游戏规则是这样的:开始时物品可以在任意一人手上,他可把物......
  • 表达式的值【题解】
    [NOIP2011普及组]表达式的值题目描述对于1位二进制变量定义两种运算:运算的优先级是:先计算括号内的,再计算括号外的。“×”运算优先于“⊕”运算,即计算表达式......