题解 e
2024-09-08 04:51:15
第一眼看貌似可以树剖，然而那个绝对值不知怎么维护
求最小连通块我只会\(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;
}
最新文章
- 个人整理的一些web前端面试题
- Codeforces Round #361 Jul.6th B题 ☺译
- Oracle 违反协议 OALL8 处于不一致状态
- csharp: NHibernate and Entity Framework (EF) (object-relational mapper)
- Ubuntu 卸载 VMware
- Cache
- Mac system快捷键
- delete 用法
- Struts2、spring2、hibernate3在SSH中各起什么作用
- 使用C语言编写windows服务一般框架
- MySQL5.6生产库自动化安装部署
- Asp.net mvc 下载文件
- Windows Server 2016-图形化备份域控制器
- RabbitMQ框架构建系列（一）——AMPQ协议
- spring 406 (Not Acceptable)错误
- mysql排序（四）
- 安装cmake
- 自己写bitmap
- C. Oh Those Palindromes
- 【代码审计】iCMS_v7.0.7 search.admincp.php页面存在SQL注入漏洞
热门文章
- WPF教程一：创建Hello world来理解XAML的内容及编译
- Windows环境mysql自动备份
- Python实现 利用朴素贝叶斯模型（NBC）进行问句意图分类
- 灵魂画手的零基础python教程1：关于Python学习的误区、python的优缺点、前景
- 公有云上构建云原生 AI 平台的探索与实践 - GOTC 技术论坛分享回顾
- CF1214E Petya and Construction Set题解
- spring.jpa.open-view问题
- Python RPC 不会？不妨看看这篇文章
- springboot 中 inputStream 神秘消失之谜
- dio框架访问云函数参数传递问题（以腾讯云中的云函数为例子）第一部