题解 e

本文主要是介绍题解 e，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

传送门

第一眼看貌似可以树剖，然而那个绝对值不知怎么维护
求最小连通块我只会\(k^2\)

主席树貌似可以用来查询区间内与某个数差的绝对值的最小值？
确实，每次查大于等于该数的最小数和小于等于该数的最大数即可
至于具体实现，实际上可以转化为求一个区间内最左/右边的数
很容易写出一个线段树上\(O(nlogn)\)的暴力遍历
但这里用的只要求第一个，可以按顺序找，找到第一个就跳出，单次复杂度\(O(logn)\)
至于查询区间和log划分区间间的问题，到了一个节点，如果它已经不在查询区间中，返回一个标记值即可

至于求连通块的问题：

• 一棵树上，给定n个点，求这n个点所在的最小连通块中的最值之类的东西
  其实找到它们的lca，\(O(k)\)遍历一次，每次查询一个点与lca之间的路径即可

Code:

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define N 100010
#define ll long long 
#define ld long double
#define usd unsigned
#define ull unsigned long long
//#define int long long 

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++)
char buf[1<<21], *p1=buf, *p2=buf;
inline int read() {
	int ans=0, f=1; char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();}
	while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();}
	return ans*f;
}

int n, q, typ;
int head[N], size, a[N], x[N];
struct edge{int to, next;}e[N<<1];
inline void add(int s, int t) {edge* k=&e[++size]; k->to=t; k->next=head[s]; head[s]=size;}
//struct que{int r, k; vector<int> v;}que[N];

namespace force{
	bool vis[N];
	int dfs(int u, int to, int r, int fa) {
		if (u==to) return abs(a[u]-r);
		for (int i=head[u],v,t; i; i=e[i].next) {
			v = e[i].to;
			if (v!=fa) {
				t=dfs(v, to, r, u);
				if (t!=-1) return min(t, abs(a[u]-r));
			}
		}
		return -1;
	}
	void solve() {
		for (int i=1,r,k,ans; i<=q; ++i) {
			ans=INF;
			r=read(); k=read();
			//cout<<r<<' '<<k<<endl;
			for (int j=1; j<=k; ++j) x[j]=read();
			for (int j=1; j<=k; ++j) 
				for (int h=j; h<=k; ++h) 
					ans=min(ans, dfs(x[j], x[h], r, 0));
			printf("%d\n", ans);
		}
		exit(0);
	}
}

namespace force2{
	bool vis[N];
	int rot;
	int dfs(int u, int r, int fa) {
		int ans=INF;
		if (vis[u]) ans=min(ans, abs(a[u]-r));
		for (int i=head[u],v,t; i; i=e[i].next) {
			v = e[i].to;
			if (v!=fa) {
				t=dfs(v, r, u);
				if (t!=-1) ans=min(ans, min(t, abs(a[u]-r)));
				if (!ans) return 0;
			}
		}
		return ans==INF?-1:ans;
	}
	void solve() {
		for (int i=1,r,k,ans; i<=q; ++i) {
			ans=INF;
			r=read(); k=read();
			//cout<<r<<' '<<k<<endl;
			for (int j=1; j<=k; ++j) x[j]=read(), vis[x[j]]=1;
			printf("%d\n", dfs(x[1], r, 0));
			for (int j=1; j<=k; ++j) vis[x[j]]=0;
		}
		exit(0);
	}
}

namespace task{
	int dep[N], siz[N], msiz[N], mson[N], top[N], id[N], rk[N], fa[N], tot;
	int rot[N], tot2, r[N*3], k[N*3], uni[N<<3], usize, lst;
	vector<ll> x[N*3];
	struct pst{
		int tl, tr, cnt, lson, rson;
		#define t(p) tree[p]
		#define tl(p) tree[p].tl
		#define tr(p) tree[p].tr
		#define cnt(p) tree[p].cnt
		#define l(p) tree[p].lson
		#define r(p) tree[p].rson
		#define pushup(p) cnt(p)=cnt(l(p))+cnt(r(p))
	}tree[N*80];
	int upd(int p1, int p2, int l, int r, int pos) {
		p1=++tot2; t(p1)=t(p2); tl(p1)=l; tr(p1)=r;
		if (l>=r) {cnt(p1)=cnt(p2)+1; return p1;}
		int mid=(l+r)>>1;
		if (pos<=mid) l(p1)=upd(l(p1), l(p2), l, mid, pos);
		else r(p1)=upd(r(p1), r(p2), mid+1, r, pos);
		pushup(p1);
		return p1;
	}
	int qleft(int p1, int p2, int l, int r) {
		//cout<<"qleft "<<p1<<' '<<p2<<' '<<l<<' '<<r<<endl;
		if (l>tr(p2) || r<tl(p2)) return 0;
		if (tl(p2)==tr(p2)) {/*cout<<"return "<<cnt(p2)-cnt(p1)<<' '<<tl(p2)<<endl;*/ return (cnt(p2)-cnt(p1))?tl(p2):0;}
		int mid=(tl(p2)+tr(p2))>>1, ans=INF, t;
		if (l<=mid && cnt(l(p2))-cnt(l(p1))) {t=qleft(l(p1), l(p2), l, r); ans=min(ans, !t?INF:t);}
		if (ans!=INF) return ans;
		if (r>mid && cnt(r(p2))-cnt(r(p1))) {t=qleft(r(p1), r(p2), l, r); ans=min(ans, !t?INF:t);}
		//puts("error");
		return ans==INF?0:ans;
	}
	int qright(int p1, int p2, int l, int r) {
		//cout<<"qright: "<<p1<<' '<<p2<<' '<<l<<' '<<r<<endl;
		if (l>tr(p2) || r<tl(p2)) return 0;
		if (tl(p2)==tr(p2)) {/*cout<<"return "<<cnt(p2)-cnt(p1)<<' '<<tl(p2)<<endl;*/ return (cnt(p2)-cnt(p1))?tl(p2):0;}
		int mid=(tl(p2)+tr(p2))>>1, ans=0, t;
		if (r>mid && cnt(r(p2))-cnt(r(p1))) {t=qright(r(p1), r(p2), l, r); ans=max(ans, t);}
		if (ans) return ans;
		if (l<=mid && cnt(l(p2))-cnt(l(p1))) {t=qright(l(p1), l(p2), l, r); ans=max(ans, t);}
		//puts("error");
		return ans;
	}
	void dfs1(int u, int pa) {
		siz[u]=1;
		for (int i=head[u],v; i; i=e[i].next) {
			v = e[i].to;
			if (v==pa) continue;
			dep[v]=dep[u]+1; fa[v]=u;
			dfs1(v, u);
			siz[u]+=siz[v];
			if (siz[v]>msiz[u]) msiz[u]=siz[v], mson[u]=v;
		}
	}
	void dfs2(int u, int f, int t) {
		top[u]=t;
		id[u]=++tot;
		rot[tot]=upd(rot[tot], rot[tot-1], 1, usize, lower_bound(uni+1, uni+usize+1, a[u])-uni);
		//cout<<"upd: "<<tot<<' '<<u<<' '<<lower_bound(uni+1, uni+usize+1, a[u])-uni<<' '<<uni[lower_bound(uni+1, uni+usize+1, a[u])-uni]<<endl;
		rk[tot]=u;
		if (!mson[u]) return ;
		dfs2(mson[u], u, t);
		for (int i=head[u],v; i; i=e[i].next) {
			v = e[i].to;
			if (v!=f && v!=mson[u]) dfs2(v, u, v);
		}
	}
	int query(int a, int b, int r) {
		//cout<<"query "<<a<<' '<<b<<' '<<r<<endl;
		int ans=INF, q1, q2;
		int rb=lower_bound(uni+1, uni+usize+1, r)-uni;
		//cout<<"rb: "<<rb<<endl;
		while (top[a]!=top[b]) {
			if (dep[top[a]]<dep[top[b]]) swap(a, b);
			//cout<<"qid: "<<id[top[a]]<<' '<<id[a]<<endl;
			q1=qleft(rot[id[top[a]]-1], rot[id[a]], rb, usize), q2=qright(rot[id[top[a]]-1], rot[id[a]], 1, rb);
			//cout<<"q1q2: "<<q1<<' '<<q2<<endl;
			ans=min(ans, min(q1?(uni[q1]-r):INF, q2?(r-uni[q2]):INF));
			if (!ans) return 0;
			a = fa[top[a]];
		}
		if (dep[a]>dep[b]) swap(a, b);
		//cout<<"qid: "<<id[a]<<' '<<id[b]<<endl;
		q1=qleft(rot[id[a]-1], rot[id[b]], rb, usize), q2=qright(rot[id[a]-1], rot[id[b]], 1, rb);
		//cout<<"q1q2: "<<q1<<' '<<q2<<endl;
		ans=min(ans, min(q1?(uni[q1]-r):INF, q2?(r-uni[q2]):INF));
		return ans;
	}
	int lca(int a, int b) {
		while (top[a]!=top[b]) {
			if (dep[top[a]]<dep[top[b]]) swap(a, b);
			a = fa[top[a]];
		}
		if (dep[a]>dep[b]) swap(a, b);
		return a;
	}
	void init() {
		dep[1]=1;
		dfs1(1, 0);
		dfs2(1, 0, 1);
	}
	void solve() {
		for (int i=1; i<=q; ++i) {
			r[i]=read(); k[i]=read(); uni[++usize]=r[i];
			for (int j=1,t; j<=k[i]; ++j) {t=read(); x[i].push_back(t);}
		}
		for (int i=1; i<=n; ++i) uni[++usize]=a[i];
		//cout<<"usize: "<<usize<<endl;
		//cout<<"uni: "; for (int i=1; i<=usize; ++i) cout<<uni[i]<<' '; cout<<endl;
		sort(uni+1, uni+usize+1);
		usize=unique(uni+1, uni+usize+1)-uni-1;
		//cout<<"usize: "<<usize<<endl;
		//cout<<"uni: "; for (int i=1; i<=usize; ++i) cout<<uni[i]<<' '; cout<<endl;
		init();
		for (int i=1,anc,ans; i<=q; ++i) {
			anc=(x[i][0]-1+lst*typ)%n+1, ans=INF;
			for (int j=1; j<k[i]&&anc!=1; ++j) anc=lca(anc, (x[i][j]-1+lst*typ)%n+1);
			//cout<<"anc: "<<anc<<endl;
			for (int j=0; j<k[i]&&ans; ++j) ans=min(ans, query((x[i][j]-1+lst*typ)%n+1, anc, r[i])); //, cout<<"nowans: "<<ans<<endl;
			printf("%d\n", ans);
			lst=ans;
		}
		//cout<<qleft(rot[0], rot[3], 1, 5)<<endl;
		//cout<<qright(rot[1], rot[3], 1, 3)<<endl;
	}
}

signed main()
{
	#ifdef DEBUG
	freopen("1.in", "r", stdin);
	#endif
	bool same=1, less1=1, ris1=1, chain=1;
	
	n=read(); q=read(); typ=read();
	if (!q) return 0;
	for (int i=1; i<=n; ++i) {
		a[i]=read();
		if (i!=1 && a[i]!=a[i-1]) same=0;
	}
	for (int i=1,u,v; i<n; ++i) {
		u=read(); v=read();
		add(u, v); add(v, u);
		if (v!=u+1) chain=0;
	}
	task::solve();
	#if 0
	if (n<=1000) force2::solve();
	for (int i=1,r,k; i<=q; ++i) {
		r=read(); k=read();
		for (int j=1; j<=k; ++j) x[j]=read(), force2::vis[x[j]]=1;
		if (!k) continue;
		else if (k==1 || same) printf("%d\n", abs(a[x[1]]-r));
		else printf("%d\n", force2::dfs(x[1], r, 0));
		for (int j=1; j<=k; ++j) force2::vis[x[j]]=0;
		//else if (r==1) printf("%d\n", task2::qmin(1, 
	}
	#endif

	return 0;
}

这篇关于题解 e的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！