Milk Visits G
2021/10/3 6:41:20
本文主要是介绍Milk Visits G,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Milk Visits G
题意
给定一棵 \(N\) 个节点的树,每个节点有一个权值。有 \(Q\) 次询问,每个询问包含三个参数 \(s1,s2,val\) ,询问 \(s1\) 到 \(s2\) 的简单路径上包不包含权值为 \(val\) 的节点。
数据范围:\(N,Q\le 10^5\)。
解法
专门来写一篇题解,特别是现在已经困得不行的时候写一篇题解,是为了复习一个知识点,就是对于互相独立的询问进行离散化处理。昨天考试三道题有两道都是离线加数据结构,那再练习一道离线题目也显得十分必要了。
树上路径,想到用树链剖分,但普通树链剖分(或者说普通线段树)无法维护如此多的信息,再加上这些询问本身互相独立(因为无后效性且不带修改),于是想到离线求解。
怎么离线?个人理解就是把有相同部分的问题放到一起集中处理或者按顺序处理。应用到本题就是把那些 \(val\) 相同的(本题解所引用的变量名都是“题意”部分里的含义,如造成阅读不便,见谅)询问放到一起。于是便有了一个比暴力稍微好一点的做法,就是对于每个 \(val\) ,暴力重新建树,把那些权值刚好为 \(val\) 的节点在树链剖分所成的线段树上标为 \(1\) ,否则为 \(0\) 。至于查询,就是标准的树链剖分查询,每次查询线段树上某个区间内是否有 \(1\) 即可。
但很明显,这样会超时。于是考虑一下这个算法复杂度高在哪里,经过观察发现它复杂度高在重新建树部分,那下一步就可以思考,真的有必要重新建树吗,或者说咱能不能在已有的那棵线段树上进行修改呢?
答案是可以的。考虑将查询按 \(val\) 升序排序,从前向后处理,对于当前的这个询问,假如这个询问的三个参数就是 \(s1,s2,val\) ,那么可以确定的是,当前线段树里没有比 \(val\) 更大权值的节点(很好理解),那么假如一条路径上有 \(val\) ,那么这个点一定会是这个区间里点权最大的点。
这样一来,问题就明朗得多了。总结一下,我们应该先把所有点权小于等于当前询问 \(val\) 的点加入线段树里,然后要做的就是查询这条路径( \(s1,s2\) 之间的简单路径)上的最大点权,这一点可以用树链剖分维护,然后看这个最大值是否等于当前询问的 \(val\) ,然后就可以得出答案。
复杂度 \(O(NlogN^2)\)。
我觉得我已经讲得比较清楚了,代码实现应该不算太难吧。
放上我丑陋的代码。AC记录
#include<cstdio> #include<algorithm> //#define zczc using namespace std; const int N=100010; inline void read(int &wh){ wh=0;int f=1;char w=getchar(); while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();} while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar(); } wh*=f;return; } inline int max(int s1,int s2){ return s1<s2?s2:s1; } inline void swap(int &s1,int &s2){ int s3=s1;s1=s2;s2=s3;return; } int m,n; struct inf{ int wh,data; }a[N]; inline bool cmpinf(inf s1,inf s2){ return s1.data<s2.data; } struct edge{ int t,next; }e[N<<1]; int head[N],esum; inline void add(int fr,int to){ esum++; e[esum].t=to; e[esum].next=head[fr]; head[fr]=esum; return; } struct ask{ int wh,s1,s2,val; }q[N]; inline bool cmpask(ask s1,ask s2){ return s1.val<s2.val; } int f[N],d[N],size[N],son[N]; void dfs1(int wh,int fa,int deep){ f[wh]=fa;d[wh]=deep;size[wh]=1; int bigson=0; for(int i=head[wh],th;i;i=e[i].next){ th=e[i].t; if(th==fa)continue; dfs1(th,wh,deep+1); size[wh]+=size[th]; if(size[th]>bigson){ bigson=size[th];son[wh]=th; } } return; } int cnt,id[N],s[N],top[N]; void dfs2(int wh,int fa,int ntop){ id[wh]=++cnt;s[cnt]=wh;top[wh]=ntop; if(son[wh])dfs2(son[wh],wh,ntop); for(int i=head[wh],th;i;i=e[i].next){ th=e[i].t; if(th==fa||th==son[wh])continue; dfs2(th,wh,th); } return; } #define lc (wh<<1) #define rc (wh<<1|1) #define mid (t[wh].l+t[wh].r>>1) struct node{ int l,r,data; }t[N<<2]; inline void pushup(int wh){ t[wh].data=max(t[lc].data,t[rc].data); return; } void build(int wh,int l,int r){ t[wh].l=l,t[wh].r=r,t[wh].data=0; if(l==r)return; build(lc,l,mid); build(rc,mid+1,r); return; } void change(int wh,int pl,int val){ if(t[wh].l==t[wh].r){ t[wh].data=max(t[wh].data,val); return; } if(pl<=mid)change(lc,pl,val); else change(rc,pl,val); pushup(wh); return; } int work(int wh,int wl,int wr){ if(wl<=t[wh].l&&t[wh].r<=wr){ return t[wh].data; } int an=0; if(wl<=mid)an=max(an,work(lc,wl,wr)); if(wr>mid)an=max(an,work(rc,wl,wr)); return an; } #undef lc #undef rc #undef mid bool ans[N]; signed main(){ #ifdef zczc freopen("in.txt","r",stdin); #endif read(m);read(n); for(int i=1;i<=m;i++){ read(a[i].data); a[i].wh=i; } sort(a+1,a+m+1,cmpinf); int s1,s2; for(int i=1;i<m;i++){ read(s1);read(s2); add(s1,s2);add(s2,s1); } for(int i=1;i<=n;i++){ read(q[i].s1);read(q[i].s2);read(q[i].val);q[i].wh=i; } sort(q+1,q+n+1,cmpask); dfs1(1,0,1); dfs2(1,0,1); build(1,1,m); int now=1; //for(int i=1;i<=m;i++)printf("%d\n",d[i]); for(int i=1;i<=n;i++){ while(now<=m&&a[now].data<=q[i].val){ //printf("working"); change(1,id[a[now].wh],a[now].data); now++; } int an=0; s1=q[i].s1,s2=q[i].s2; while(top[s1]!=top[s2]){ //printf("working"); //printf("c:%d %d\n",top[s1],top[s2]); if(d[top[s1]]<d[top[s2]])swap(s1,s2); an=max(an,work(1,id[top[s1]],id[s1])); s1=f[top[s1]]; } if(d[s1]<d[s2])swap(s1,s2); //printf("%d %d\n",s1,s2); an=max(an,work(1,id[s2],id[s1])); //printf("now:%d %d %d\n",q[i].wh,q[i].val,an); ans[q[i].wh]=(an==q[i].val); } for(int i=1;i<=n;i++)printf("%d",ans[i]); return 0; }
这篇关于Milk Visits G的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?