首页 > 其他分享 >成都七中 解题报告

成都七中 解题报告

时间:2023-02-11 22:13:17浏览次数:39  
标签:rt 七中 int void 成都 解题 maxn id mx

点分树有这么一个性质:你总能找到一个点,使得原树中这个点所在的连通块在这个点的子树内(如果整棵树没有被破坏,这个点就是根节点)。

这个结论过于显然,证明只有一句话:点分树上的联通就是原树上的联通,如果有在子树外的点,就一定是上方的点,所以还是有这么一个点存在。

那么显然,把询问放到原来的点上和放到这个点上,答案都是一样的,但放到这个点上就只需要处理子树上的问题了,所以我们把询问移动一下。

至于怎么找到这个点呢?在点分治时,我们可以统计当前根节点到可到达的点(点分树上的子树)的距离,给这些点开个 vector,把根和根到这个点路径上的最大最小值塞进去,之后如果这个点有询问,就把这些值取出来一一比较就行。

之前其实我也尝试过在点分树上暴力跳父亲的做法,但是点分树上的距离跟原树没有关系,也就是说还是要通过倍增计算两点路径上的最大最小值,实在算不动了,于是换了种方法。

这样搞完以后我们顺便记录一下点分树子树到根节点路径上的最大最小值,再加一个颜色,以后计算根节点的答案时就不用再遍历子树了。

现在对于每个节点,我们有她子树里每个节点的颜色与路径上大小值,我们还有“寄居”在这个节点上的问题,于是问题变成了:

给你 \(n\) 个结构体,每个结构体含有三个变量:\(l,r,col\)。再给你 \(m\) 个询问 \(ql,qr\),询问 \(l >= ql\) 且 \(r <= qr\) 的元素的 \(col\) 种类数。


据说这是个喜闻乐见的二维偏序,但我还是推了半个小时。。。下面是推出来的结果:

回忆 HH的项链(区间数颜色) 一题,我们可以设一个数组,表示每种颜色上一个元素在哪里,如果有更优的就可以替代掉。

接着,我们用将 \(l\) 从大到小排序解决 \(l>=ql\) 的限制,在新元素加入进来时与原来的元素进行比较(如果有的话),如果 \(r\) 比原元素小说明更优,就将其放到 \(r\) 的位置。然后随着 \(l\) 的变化,用树状数组统计和输进答案里就行。


可以看出这道题所有部分都可以在点分治上完成,但思想和点分树息息相关。

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define mp make_pair
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Rep(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
void INIT()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
}
const int maxn = 100105;
int n, m;
int col[maxn];
int root;
vector<int> e[maxn], t[maxn];
bool vis[maxn];
int rt, mx[maxn], si[maxn], trTot, dep[maxn];
void findDeep(int u, int fa)
{
	mn[u][0] = mxx[u][0] = u;
	for (auto v : e[u])
	{
		if (v == fa)
			continue;
		pa[v][0] = u;
		dep[v] = dep[u] + 1;
		findDeep(v, u);
	}
}
int Tot;
void findRt(int u, int fa)
{
	mx[u] = 0;
	si[u] = 1;
	for (auto v : e[u])
	{
		if (vis[v] || v == fa)
			continue;
		findRt(v, u);
		si[u] += si[v];
		if (si[v] > mx[u])
			mx[u] = si[v];
	}
	mx[u] = max(mx[u], Tot - si[u]);
	if (mx[rt] > mx[u])
		rt = u;
}
struct pp
{
	int l, r, id;
};
vector<pp> w[maxn];
vector<pp> et[maxn];
void youcanttakemyAC(int u, int f, int mn, int mx)
{
	w[rt].push_back(pp{mn, mx, col[u]});
	et[u].push_back(pp{mn, mx, rt});
	for(auto v : e[u])
	{
		if(vis[v] == 1 || f == v) continue;
		youcanttakemyAC(v, u, min(mn, v), max(mx, v));
	}
}
void you(int u)
{
	rt = u;
	for(auto v : e[u])
	{
		if (vis[v] == 1)
			continue;
		youcanttakemyAC(v, u, min(v, u), max(v, u));
	}
}
int fa[maxn];
void build(int u)
{
	w[u].push_back(pp{u, u, col[u]});
	et[u].push_back(pp{u, u, u});

	vis[u] = 1;
	you(u);
	for (auto v : e[u])
	{
		if (vis[v] == 1)
			continue;
		rt = 0;
		Tot = si[v];
		findRt(v, u);
		fa[rt] = u;
		t[u].push_back(rt);
		t[rt].push_back(u);
		build(rt);
	}
}
void read()
{
	cin >> n >> m;
	int u, v;
	for (int i = 1; i <= n; i++)
		cin >> col[i];
	For(i, 1, n - 1)
	{
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
}
void Build()
{
	rt = 0;
	mx[0] = 2147483647;
	findDeep(1, -1);
	init();
	Tot = n;
	findRt(1, -1);
	root = rt;
	build(rt);
}
int ans[maxn];
void try_to_jump(int l, int r, int &x)
{
	while (fa[x] && fa[x] >= l && fa[x] <= r)
		x = fa[x];
}
struct tree
{
#define lowbit(x) (x & (-x))
	int tr[maxn];
	void add(int u, int k)
	{
		for (; u <= n; u += lowbit(u))
			tr[u] += k;
	}
	void re(int u)
	{
		for (; u <= n; u += lowbit(u))
			tr[u] = 0;
	}
	int que(int u)
	{
		int ans = 0;
		for (; u >= 1; u -= lowbit(u))
			ans += tr[u];
		return ans;
	}
} p;
bool cmp(pp a, pp b)
{
	return a.l > b.l || (a.l == b.l && a.id > b.id);//先要算完贡献再询问
}
int tmd[maxn];
int main()
{
	freopen("text.in", "r", stdin);
	INIT();
	read();
	Build();
	int l, r, x;
	for (int i = 1; i <= m; i++)
	{
		cin >> l >> r >> x;
		for(auto j : et[x])
		{
			// cout << x << ' ' << j.l << ' ' << j.r << ' ' << j.id << endl;
			if(j.l >= l && j.r <= r)
			{
				// cout << j.id << endl;
				w[j.id].push_back(pp{l, r, -i});
				break;//先进来的深度小,最先进来的深度最小
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		sort(w[i].begin(), w[i].end(), cmp);
		for(auto j : w[i]) 
		{
			if(j.id < 0)
				ans[-j.id] = p.que(j.r);//用正负判断是询问还是子树元素,就可以一起排序了!
			else 
			{
				if(!tmd[j.id] || tmd[j.id] > j.r) 
				{
					if(tmd[j.id]) p.add(tmd[j.id], -1);
					tmd[j.id] = j.r;
					p.add(tmd[j.id], 1);
				}
			}
		}
		for(auto j : w[i])
			if(j.id > 0 && tmd[j.id]) 
			{
				p.add(tmd[j.id], -1);
				tmd[j.id] = 0;
			}
	}
	for (int i = 1; i <= m; i++)
		cout << ans[i] << endl;
	return 0;
}

如何判断两种方法哪个实现简单?看看哪个方法让你建立的额外的函数多就行了。

大家可不要和我一样犯调 2 个小时后重构的失误哦!

标签:rt,七中,int,void,成都,解题,maxn,id,mx
From: https://www.cnblogs.com/closureshop/p/17112677.html

相关文章

  • CF1781D 解题乱弹
    abc1057510554老师说,搞这种数论题,就可以在CF上numbertheory板刷一个1300-1900就可以了。然后发现连1800的题都做不出来,我可以退役力QAQ观察到\(n\)很小,也......
  • 剑指 Offer 32 - I. 从上到下打印二叉树(java解题)
    目录1.题目2.解题思路3.数据类型功能函数总结4.java代码1.题目从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。 例如:给定二叉树: [3,9,......
  • 「解题报告」[省选联考 2021 A 卷] 矩阵游戏
    啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会了!啥都不会......
  • [POI2011]MET-Meteors 解题报告
    语言系统紊乱了QAQ这道题感觉不是很难鸭qwq。先只考虑一个国家,怎么做?很显然,就直接二分一下就行了。判定答案可以维护一个差分数组,然后最后对它做一个前缀和,再求一下这......
  • USACO23 JAN 解题报告
    T1FindandReplaceG个人思路:从后往前做,每次修改,替换前一个修改里面的字母,显然是错的,因为没替换更前面的字母。然后就想不出来了。正解:第\(i\)次修改\(c,s\),相当......
  • 「解题报告」[省选联考 2022] 序列变换
    我不是很能理解?神奇贪心题。括号序列考虑直接整树形结构,然后操作就是将一个子树内所有儿子放到另一颗子树里,并把这个点单独放到这个子树内,贡献为\(x\)乘终点子树权值加......
  • loj#6739. 圆环之理 解题报告
    发现之前写过这题题解,今天突然记起这道题就发出来一下。其实基本上是复读一遍EI题解(题意一个长度为\(n\)的环上等距排列\(n\)个点,任意两点之间均有一条无向边。每......
  • 蓝桥杯题目——飞行员兄弟解题详解及其包含的思想
    前言本文介绍蓝桥杯题目——飞行员兄弟的解题方法及其包含的代码思想。题目信息“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有16个把手的冰箱。已知每个把手可以......
  • 「解题报告」[省选联考 2022] 卡牌
    放假上午想出的做法,写了一下TLE35分。以为有更高级的复杂度,然后刚看了看题解发现题解就是这个复杂度,呃呃,卡常吧。考虑将每个数写成它所包含的质因子的集合,写成一个0......
  • P2617 Dynamic Rankings 解题报告
    link整体二分是一种东西,比如上面这道题。先考虑一个不带修版本的,也就是经典问题区间kth,显然我们可以主席树但是我知道你很想用主席树但是你先别用不用主席树,用一种离线......