1 条题解

  • 0
    @ 2025-8-24 22:56:44

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar 封禁用户
    None

    搬运于2025-08-24 22:56:44，当前版本为作者最后更新于2025-01-13 21:45:08，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    @代表元思想

    思路：

    先概括一下模型：满足某种条件的区间极大连通块计数。

    *极大 = 划分 -> 标志物（把一个序列划分到标志物的左/右等） -> 最高点。

    由于一个点只能唯一属于一个极大连通块，所以考虑通过统计最高点以统计连通块。

    由于 depdep 可能有相同的，于是用 bfnbfn 比较。

    模型转化完毕，把条件重新总结一下：

    • 对于一个 u∈[l,r] u \in [l, r] ，若不存在一个满足以下条件的 vv，则 uu 是 [l,r][l, r] 的一个答案：

      • v∈[l,r]v\in[l, r]

      • dis(v,u)≤kdis(v, u)\le k

      • bfnv<bfnubfn_v < bfn_u

    显然考虑预处理 + 查询，观察到 [l,r][l, r] 的后效性不强（指 l,r 都没有参与剩下条件的运算），于是考虑一个小 Trick：

    • 可以预处理出 Lu,RuL_u, R_u 表示满足剩余条件时 l,r 最多能取到哪里。

    然后查询：

    • ans=∑u=lr[Lu≤l]⋅[r≤Ru]ans = \sum_{u=l}^r [L_u\le l]\cdot [r\le R_u]

    • 三维偏序，使用容斥优化。

    • $ans = (r-l+1) - \sum_{u=l}^r [l<L_u] - \sum_{u=l}^r [R_u<r] + \sum_{u=l}^r [l<L_u]\cdot [R_u<r] $

    • 发现最后那个 uu 的范围可以扩展到 [1,n][1, n] ，所以实际上是二维偏序，如下：

    • $ans = (r-l+1) - \sum_{u=l}^r [l<L_u] - \sum_{u=l}^r [R_u<r] + \sum_{u=1}^n [l<L_u]\cdot [R_u<r] $

    • 二维偏序，直接树状数组即可。

    考虑预处理：

    • 求 Lu,RuL_u, R_u 相当于求离 uu 最近的满足上述条件后两个条件的元素。

    • 由于限制中有与距离相关的邻域信息，考虑使用点分治/点分树维护。

    • 对于限制 dis(v,u)≤kdis(v, u) \le k ：

      • 在每个点分祖先处维护一个以元素编号为下标的线段树。

      • 查询时枚举每个点分祖先后在线段树上二分即可。

    • 对于另一限制 bfnv<bfnubfn_v < bfn_u ：

      • 发现我们只要保证目前线段树里的元素的 bfn 都 < bfnubfn_u 即可。

      • 于是考虑在预处理扫描线时按照 bfn 的顺序即可。

    优化/卡常：

    • 空间：

      • 显然现在的空间复杂度是 O(nlog⁡2n)O(n\log^2 n) 的，不能通过。

      • 我们现在是对每个元素去遍历它的点分祖先，由于所有祖先都要存下来，很浪费空间。

      • 考虑正难则反，对于每个点分祖先，去给它的所有点分子树提供贡献。

      • 这样每次就只用一棵线段树，是 O(n)O(n) 的。

    • 时间：

      • 线段树可以写非递归。

      • 点分治在遍历当前点分祖先所管辖的元素时，在 depu>Kdep_u > K 后就可以不遍历后面的子树了，直接 return。

      • 如果当前的 Lu/RuL_u/R_u 已经等于 u−1/u+1u-1/u+1 了，就不用再更新了。

    Code：

    #include<bits/stdc++.h>
#define ll long long
using namespace std;

const int Maxn = 3e5+5, Maxq = 6e5+5;

namespace EDGE {
	int sz, head[Maxn];
	struct Edge { int next, to; } edge[Maxn*2];
	inline void Add_edge(int u, int v) {
		edge[++sz] = {head[u], v};
		head[u] = sz;
	}
} using namespace EDGE;

class SegmentTree {
private:
	const int INF = INT_MAX/2-5; int cnt, rt, limit;
	struct Segment { int ls, rs, mn; } seg[Maxn<<2];
	inline void newnode(int &t) {
		t = ++cnt, seg[t].ls = seg[t].rs = 0, seg[t].mn = INF;
	}
	inline int Queryl(int t, int l, int r, int L, int R, int val) {
		if(!t || r<L || R<l || (seg[t].mn > val))	return 0;
		if(L<=l and r<=R) {
			for(int mid; l^r; ) {
				// printf("t:%d, l:%d, r:%d, mn:%d, val:%d\n", t, l, r, seg[t].mn, val);
				mid = (l+r)>>1;
				if(seg[t].rs and seg[seg[t].rs].mn <= val)	t = seg[t].rs, l = mid+1;
				else 	t = seg[t].ls, r = mid;
			}
			// printf("l:%d, r:%d, t:%d\n", l, r, t);
			return l;
		}
		int mid = (l+r)>>1;
		int res = Queryl(seg[t].rs, mid+1, r, L, R, val);
		return res ?res :Queryl(seg[t].ls, l, mid, L, R, val);
	}
	inline int Queryr(int t, int l, int r, int L, int R, int val) {
		if(!t || r<L || R<L || (seg[t].mn > val))	return limit+1;
		if(L<=l and r<=R) {
			for(int mid; l^r; ) {
				mid = (l+r)>>1;
				if(seg[t].ls and seg[seg[t].ls].mn <= val)	t = seg[t].ls, r = mid;
				else 	t = seg[t].rs, l = mid+1;
			}
			return l;
		}
		int mid = (l+r)>>1;
		int res = Queryr(seg[t].ls, l, mid, L, R, val);
		return res!=limit+1 ?res :Queryr(seg[t].rs, mid+1, r, L, R, val);
	}
public:
	inline void init(int n) {
		limit = n, cnt = rt = 0;
	}
	inline void clear() {
		cnt = rt = 0;
	}
	inline void insert(int pos, int val) {
		if(!rt)	newnode(rt);
		int l = 1, r = limit, t = rt;
		for(int mid; ; ) {
			seg[t].mn = min(seg[t].mn, val);
			if(l == r)	return ;
			mid = (l+r)>>1;
			if(pos <= mid) {
				if(!seg[t].ls)	newnode(seg[t].ls);
				t = seg[t].ls, r = mid;
			} else {
				if(!seg[t].rs)	newnode(seg[t].rs);
				t = seg[t].rs, l = mid+1;
			}
		}
	}
	inline int Queryl(int R, int val) {
		return Queryl(rt, 1, limit, 1, R, val);
	}
	inline int Queryr(int L, int val) {
		return Queryr(rt, 1, limit, L, limit, val);
	}
} seg;

class BinaryIndexedTree {
private:
	int tree[Maxn], limit;
	inline int lowbit(int &t) { return t&(-t); }
public:
	inline void init(int n) { limit = n; }
	inline void Add(int t, int k) {
		for(; t; t-=lowbit(t))	tree[t] += k;
	}
	inline int Ask(int t) {
		int res = 0;
		for(; t<=limit; t+=lowbit(t))	res += tree[t];
		return res;
	}
} bit;

namespace Josh_zmf {
	
	int N, Q, K, mcnt, bfn[Maxn], L[Maxn], R[Maxn], dep[Maxn], ans[Maxn];
	int rt, all, stk[Maxn], top, size[Maxn]; bool vis[Maxn]; queue <int> q;
	struct Que { int l, r, id; } que[Maxq];
	struct Mod { int x, y, opt; } mod[Maxn*3];

	inline void pre_bfs(int u) {
		static int num = 0; static bool bj[Maxn];
		q.push(u);
		for(; !q.empty(); ) {
			u = q.front(), q.pop();
			bj[u] = 1, bfn[u] = ++num, L[u] = 0, R[u] = N+1;
			for(int i=head[u], v; i; i=edge[i].next) {
				v = edge[i].to;
				if(bj[v])	continue;
				q.push(v);
			}
		}
		memset(bj+1, 0, N);
	}
	
	inline void getrt(int u, int faa) {
		static int maxx[Maxn];
		size[u] = 1, maxx[u] = 0;
		for(int i=head[u], v; i; i=edge[i].next) {
			if((v=edge[i].to)==faa || vis[v])	continue;
			getrt(v, u), size[u] += size[v];
			maxx[u] = max(maxx[u], size[v]);
		}
		maxx[u] = max(maxx[u], all - size[u]);
		if(!rt || maxx[u] < maxx[rt])	rt = u;
	}

	inline void get_bfs(int u) {
		static int bj[Maxn], tim = 0;
		q.push(u), tim++, dep[u] = 1;
		for(; !q.empty(); ) {
			u = q.front(), q.pop();
			bj[u] = tim, stk[++top] = u;
			if(dep[u] >= K+1)	continue;
			for(int i=head[u], v; i; i=edge[i].next) {
				v = edge[i].to;
				if(bj[v]==tim || vis[v])	continue;
				dep[v] = dep[u] + 1, q.push(v);
			}
		}
	}

	inline void get_dfs(int u, int faa=0) {
		stk[++top] = u, dep[u] = dep[faa] + 1;
		for(int i=head[u], v; i; i=edge[i].next) {
			v = edge[i].to;
			if(v == faa || vis[v])	continue;
			get_dfs(v, u);
		}
	}
	
	inline void Build(int u) {
		vis[u] = 1;
		top = 0, get_bfs(u), sort(stk+1, stk+1+top, [&](const int &a, const int &b) { return bfn[a] < bfn[b]; } ), seg.clear();
		for(int i=1, v; i<=top; i++) {
			v = stk[i];
			// printf("u:%d, v:%d, depu:%d, depv:%d\n", u, v, dep[u], dep[v]);
			if(L[v]^(v-1))	L[v] = max(L[v], seg.Queryl(v-1, K+2*dep[u]-dep[v]));
			if(R[v]^(v+1))	R[v] = min(R[v], seg.Queryr(v+1, K+2*dep[u]-dep[v]));
			// printf("L:%d, R:%d\n", L[v], R[v]);
			seg.insert(v, dep[v]);
		}
		for(int i=head[u], v; i; i=edge[i].next) {
			v = edge[i].to;
			if(vis[v])	continue;
			all = size[v], rt = 0, getrt(v, 0), Build(rt);
		}
	}

	inline int main() {
		cin>> N>> Q>> K, seg.init(N), bit.init(N+2);
		for(int u=2, v; u<=N; u++)	cin>> v, Add_edge(u, v), Add_edge(v, u);
		pre_bfs(1), all = N, rt = 0, getrt(1, 0), Build(rt);
		// for(int u=1; u<=N; u++) { L[u]++, R[u]--; }
		// for(int u=1; u<=N; u++) {
		// 	printf("u:%d, bfn:%d, L:%d, R:%d\n", u, bfn[u], L[u], R[u]);
		// }
		for(int i=1; i<=Q; i++)	cin>> que[i].l>> que[i].r, que[i].id = i, que[i].l++, que[i].r++;
		for(int i=1; i<=N; i++)	mod[++mcnt] = {L[i]+1, i+1, 1}, mod[++mcnt] = {i+1, R[i]+1, 1}, mod[++mcnt] = {L[i]+1, R[i]+1, -1};
		sort(que+1, que+1+Q, [&](const Que &a, const Que &b) { return a.r < b.r; } );
		sort(mod+1, mod+1+mcnt, [&](const Mod &a, const Mod &b) { return a.y < b.y; } );
		for(int i=1, j=1; i<=Q; i++) {
			for(; j<=mcnt and mod[j].y<=que[i].r; j++)	bit.Add(mod[j].x, mod[j].opt);
			ans[que[i].id] = que[i].r - que[i].l + 1 - bit.Ask(que[i].l);
		}
		for(int i=1; i<=Q; i++)	cout<< ans[i]<< '\n';
		return 0;
	}

}

int main() {
	Josh_zmf::main();
	return 0;
}
    • 1

    [THUWC 2020] 某科学的动态仙人掌

    信息

    ID
    10024
    时间
    6000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 28ms