单例模式 android教程 mysql安装 EasyCVR listview random highcharts tcp merge sqlalchemy laravel4 coldfusion grunt Vanilla JS Select2 vue社区 网页后台模板 css获取最后一个元素 springboot单点登录 android富文本框架 oracle取第一条数据 webform开发教程 python3入门 python实战 python函数参数 java变量类型 java集成 java入门教程 java初级 java目录 java接口调用 莫愁脚本 嵌入式linux驱动程序设计从入门到精通 一键刷入recovery stata软件 js闭包的理解 微信python退出程序 ipad锁屏 无法打开搜索页 脚本错误怎么解决
当前位置: 首页 > 学习教程  > 编程语言

Query on A Tree(可持续01线段树+dfs序)

2021/3/4 0:02:33 文章标签:

Link 题意 给你一棵树,每个节点有权值,Q次询问,求u为跟的子树一个点与x亦或后的值最大是多少。 思路 对于异或我们很容易联想到异或, 但显然对于每个点都需要开一个01字典树, 但如果每个点都开一个01字典树来表示其…

Link

题意

给你一棵树,每个节点有权值,Q次询问,求u为跟的子树一个点与x亦或后的值最大是多少。

思路

对于异或我们很容易联想到异或, 但显然对于每个点都需要开一个01字典树, 但如果每个点都开一个01字典树来表示其子树,显然空间不够, 所以引出了可持续化01字典树,和主席树类似。
所以我们先按照前序遍历建立可持续化01字典树
然后对于每个查询 u, x
l = st[u], r = st[u];
我们用 root[l - 1]这个01字典树和root[r], 来对比出以u为根的字典树,然后直接查询最大异或值即可。
细节见于代码

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll N = 260005;
vector<int> q[N];
int n, m, t, a[N], id[N], rt[N], st[N], ed[N], b[N];

struct node 
{
	int cnt;
	int ch[N * 32][2], sum[N * 32];
	void init()
	{
		cnt = 0, b[0] = 1; // b[i], 记录第2^i
		for(int i = 1; i <= 30; i ++) b[i] = b[i - 1] * 2;
		memset(ch, 0, sizeof ch);
		memset(sum, 0, sizeof sum);
	}
	int insert_(int x, int val) // x为上一个trie树的根节点
	{
		int res, y;
		y = res = ++ cnt; // 开新点
		for(int i = 30; i >= 0; i --)
		{
			ch[y][0] = ch[x][0];
			ch[y][1] = ch[x][1];
			sum[y] = sum[x] + 1;
			int tmp = val & b[i];
			tmp >>= i; // 求出val在二进制下第i位的值
			x = ch[x][tmp]; // x(tmp方向)向下走
			ch[y][tmp] = ++ cnt; // 开点
			y = ch[y][tmp]; // y也继续向下走
		}
		sum[y] = sum[x] + 1; // 到叶子节点后, 表示在同一个位置来过的次数
		return res;
	}
	int query(int l, int r, int val)
	{
		int ans = 0;
		for(int i = 30; i >= 0; i --)
		{
			int tmp = val&b[i];
			tmp >>= i; // 取val的第i位(二进制)
			if(sum[ch[r][tmp ^ 1]] - sum[ch[l][tmp ^ 1]])
				ans += b[i], l = ch[l][tmp ^ 1], r = ch[r][tmp ^ 1];
			else
				l = ch[l][tmp], r = ch[r][tmp];
		}
		return ans;
	}
}trie;

void dfs(int u, int p) //
{
	st[u] = ++ t;//  存子树的前序遍历的起点
	id[t] = u; // 存前序遍历结果
	for(int i = 0; i < q[u].size(); i ++)
	{
		int v = q[u][i];
		if(v == p)
			continue;
		dfs(v, u);
	}
	ed[u] = t; // 存以u为根节点,子树前序遍历的终点
}

int main()
{
	int i, j, x;
	while(scanf("%d%d", &n, &m) != EOF)
	{
		t = 0;
		rt[0] = 0;
		trie.init();
		for(int i = 1; i <= n; i++)
			scanf("%d", &a[i]), q[i].clear();
		for(i = 2; i <= n; i ++)
		{
			scanf("%d", &x);
			q[x].push_back(i);
		}
		dfs(1, 0);
		for(int i = 1; i <= n; i++)
			rt[i] = trie.insert_(rt[i - 1], a[id[i]]); // 按照前序遍历,分别对每一个前序遍历的节点建一棵01字典树
		int l, r, root, x;
		while(m --)
		{
			scanf("%d%d", &root, &x);
			l = st[root];
			r = ed[root];
			printf("%d\n", trie.query(rt[l - 1], rt[r], x)); // 只需查询l ~ r 中那个
		}
	}
	return 0;
}


本文链接: http://www.dtmao.cc/news_show_763158.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?