2019CCPC Final K. Russian Dolls on the Christmas Tree

题目大意

一棵 \(n(1\leq n\leq 2\times 10^5)\) 个节点以 \(1\) 为根的树，分别求以 \(1\sim n\) 为根的子树中有多少个节点编号连续的段。 \(T(1\leq T\leq 10)\) 组数据， \(\sum_{i=1}^{T}n\leq 10^6\) 。

思路

将子树按 \(dfs\) 序转化为区间，之后求区间内有多少个数字连续的段。我们可以使用树状数组，用一个 \(vis[\space]\) 来记录每个数字是否出现过，我们对区间从前往后遍历，对于每一个数字 \(i\) ，如果 \(i-1,i+1\) 都没有出现过，说明是新的一段，于是在这个位置 \(+1\) ；如果二者仅有一个出现过，说明段数没有变化；如果都出现过，说明有两个段被合并为了一个段，于是需要在这个位置 \(-1\)。这样查询区间 \([1,x]\) 的时候就是对前 \(x\) 个位置上的数求和即可。如果查询的左端点不是 \(1\) 那么我们要考虑去掉左侧不属于查询区间部分的影响，对于其中的每一个数字 \(i\) ，其会影响到 \(i-1,i+1\) 对应位置上的值，因为 \(i\) 是更早出现的，所以此时我们把那两个值 \(+1\) , 将 \(i\) 对应位置上的值置为 \(0\) ，然后对于查询区间 \([l,r]\) ，答案依然是前 \(r\) 个值的和。我们对所有询问按查询的左端点排序，依次查询即可，复杂度 \(O(nlogn)\) 。

代码

#include<bits/stdc++.h>

#include<unordered_map>

#include<unordered_set>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int, int> PII;

#define all(x) x.begin(),x.end()

//#define int LL

//#define lc p*2+1

//#define rc p*2+2

#define endl '\n'

#define inf 0x3f3f3f3f

#define INF 0x3f3f3f3f3f3f3f3f

#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)

#pragma warning(disable :4996)

const long double eps = 1e-15;

const LL MOD = 1000000007;

const LL mod = 998244353;

const int maxn = 200010;

int T, N, cnt = 0;

vector<int>G[maxn];

int dfn[maxn], in[maxn], out[maxn], rnk = 0, A[maxn];

bool vis[maxn];

int dat[maxn], n, ans[maxn], val[maxn];

struct Query{

	int l, r, id;

}Q[maxn];

bool cmp(const Query& a, const Query& b)

{

	return a.l < b.l;

}

void add(int i, int x)

{

	while (i <= n)

	{

		dat[i] += x;

		i += i & (-i);

	}

}

int sum(int i)

{

	int ans = 0;

	while (i)

	{

		ans += dat[i];

		i -= i & (-i);

	}

	return ans;

}

void add_edge(int from, int to)

{

	G[from].push_back(to);

	G[to].push_back(from);

}

void dfs(int v, int p)

{

	in[v] = dfn[v] = ++rnk;

	A[dfn[v]] = v;

	val[dfn[v]] = 0;

	for (int i = 0; i < G[v].size(); i++)

	{

		int to = G[v][i];

		if (to == p)

			continue;

		dfs(to, v);

	}

	out[v] = rnk;

}

void solve()

{

	rnk = 0;

	dfs(1, 0);

	n = N;

	for (int i = 1; i <= N; i++)

	{

		if (!vis[A[i] + 1] && !vis[A[i] - 1])

		{

			add(i, 1);

			val[i]++;

		}

		else if (vis[A[i] + 1] && vis[A[i] - 1])

		{

			add(i, -1);

			val[i]--;

		}

		vis[A[i]] = true;

	}

	for (int i = 1; i <= N; i++)

		Q[i] = Query({ in[i], out[i], i });

	sort(Q + 1, Q + N + 1, cmp);

	int nl = 1;

	for (int i = 1; i <= N; i++)

	{

		int l = Q[i].l, r = Q[i].r;

		while (nl < l)

		{

			if (A[nl] != N && dfn[A[nl] + 1] > nl)

			{

				add(dfn[A[nl] + 1], 1);

				val[dfn[A[nl] + 1]]++;

			}

			if (A[nl] != 1 && dfn[A[nl] - 1] > nl)

			{

				add(dfn[A[nl] - 1], 1);

				val[dfn[A[nl] - 1]]++;

			}

			add(nl, -val[nl]);

			val[nl] = 0;

			nl++;

		}

		ans[Q[i].id] = sum(r);

	}

	cout << "Case #" << cnt << ": ";

	for (int i = 1; i <= N; i++)

		cout << ans[i] << (i == N ? endl : ' ');

}

int main()

{

	IOS;

	cin >> T;

	while (T--)

	{

		memset(vis, false, sizeof(vis));

		memset(dat, 0, sizeof(dat));

		cnt++;

		cin >> N;

		int u, v;

		for (int i = 1; i <= N; i++)

			G[i].clear();

		for (int i = 1; i < N; i++)

		{

			cin >> u >> v;

			add_edge(u, v);

		}

		solve();

	}

	return 0;

}

巴特西

2019CCPC Final K. Russian Dolls on the Christmas Tree

题目大意

思路

代码

最新文章

热门文章