【题解】Luogu P5360 [SDOI2019]世界地图
2024-08-31 20:39:39
原题传送门
每次查询的实际就是将地图的一个前缀和一个后缀合并后的图的最小生成树边权和
我们要预处理每个前缀和后缀的最小生成树
实际求前缀和（后缀和）的过程珂以理解为上一个前缀和这一列的最小生成树进行合并，实际最后前缀和后缀合并也是这样
如果暴力进行合并的话，每次边数是nm级别的，明显会TLE和MLE
我们考虑一下，实际每次合并主要和最左、最右两列（称这些点为关键点）有关，每次合并，原来最小生树中有可能会有一些边要删掉使得合并后是最小生成树。感性理解一下，珂能删掉的边一定在两个关键点在原来最小生成树之间的链上，所以我们对关键点建最小生成树的虚树，边权为原来最小生成树之间两点边权的最大值，其他的边权累加成和即可（因为其他的边不珂能删掉），这时两个最小生成树的边数的数量级都是n*常数的，所以直接暴力kruscal。
这个算法的复杂度大概为\(O(n*(m+q)\log n)\)
#include <bits/stdc++.h>
#define N 10005
#define ll long long
using namespace std;
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[20];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Max(register int a,register int b)
{
return a>b?a:b;
}
int n,m,q,foo[N][105],bar[N][105];
unsigned int SA,SB,SC;
int lim;
inline int rng()
{
SA^=SA<<16;SA^=SA>>5;SA^=SA<<1;
unsigned int t=SA;SA=SB;SB=SC;SC^=t^SA;
return SC%lim+1;
}
struct edge{
int u,v,w;
bool operator < (const edge &b)const{return w<b.w;}
};
struct MST{
int tot;
ll sum;
vector <edge> E;
MST(){}
MST(register int *c)
{
tot=n,sum=0;
for(register int i=1;i<n;++i)
E.push_back((edge){i,i+1,c[i]});
}
inline ll query()
{
ll res=sum;
for(register int i=0;i<E.size();++i)
res+=E[i].w;
return res;
}
}pre[N],suf[N];
int tot,fa[N],mrk[N],to[N],nxt[N],ww[N],head[N],cnt;
vector <edge> E;
ll ans;
inline int find(register int x)
{
return x==fa[x]?x:fa[x]=find(fa[x]);
}
inline void link(register edge x)
{
to[++cnt]=x.v,nxt[cnt]=head[x.u],ww[cnt]=x.w,head[x.u]=cnt;
to[++cnt]=x.u,nxt[cnt]=head[x.v],ww[cnt]=x.w,head[x.v]=cnt;
ans+=x.w;
}
inline bool dfs1(register int u,register int f)
{
int s=0;
for(register int e=head[u];e;e=nxt[e])
if(to[e]!=f)
s+=dfs1(to[e],u);
mrk[u]|=(s>=2);
s+=mrk[u];
return s;
}
inline void dfs2(register int u,register int f,register int lst,register int val)
{
if(mrk[u])
{
if(lst)
E.push_back((edge){mrk[u],lst,val});
lst=mrk[u];
ans-=val;
val=0;
}
for(register int e=head[u];e;e=nxt[e])
if(to[e]!=f)
dfs2(to[e],u,lst,Max(val,ww[e]));
}
inline MST merge(register MST a,register MST b,register int *c)
{
tot=a.tot+b.tot;
E.clear();
for(register int i=0;i<a.E.size();++i)
E.push_back(a.E[i]);
for(register int i=0;i<b.E.size();++i)
E.push_back((edge){b.E[i].u+a.tot,b.E[i].v+a.tot,b.E[i].w});
for(register int i=1;i<=n;++i)
E.push_back((edge){a.tot-n+i,a.tot+i,c[i]});
sort(E.begin(),E.end());
for(register int i=1;i<=tot;++i)
fa[i]=i,mrk[i]=(i<=n||i>tot-n),head[i]=0;
cnt=ans=0;
for(register int i=0;i<E.size();++i)
{
edge x=E[i];
if(find(x.u)!=find(x.v))
link(x),fa[find(x.u)]=find(x.v);
}
dfs1(1,0);
cnt=0;
for(register int i=1;i<=tot;++i)
if(mrk[i])
mrk[i]=++cnt;
E.clear();
dfs2(1,0,0,0);
MST res;
res.tot=cnt;
res.sum=a.sum+b.sum+ans;
res.E=E;
return res;
}
int main()
{
n=read(),m=read();
scanf("%u%u%u",&SA,&SB,&SC);
lim=read();
for(register int i=1;i<=n;++i)
for(register int j=1;j<=m;++j)
foo[j][i]=rng();
for(register int i=1;i<n;++i)
for(register int j=1;j<=m;++j)
bar[j][i]=rng();
pre[1]=MST(bar[1]),suf[m]=MST(bar[m]);
for(register int i=2;i<m;++i)
pre[i]=merge(pre[i-1],MST(bar[i]),foo[i-1]);
for(register int i=m-1;i>1;--i)
suf[i]=merge(MST(bar[i]),suf[i+1],foo[i]);
q=read();
while(q--)
{
int l=read(),r=read();
write(merge(suf[r+1],pre[l-1],foo[m]).query()),puts("");
}
return 0;
}
最新文章
- VMware创建Linux虚拟机并安装CentOS(三)
- 用扩展开发一个PHP类
- ClippingNode实现新手引导高亮裁切
- eclipse将编辑栏一分为二
- 关于vs2010 起始页
- [转] 用SBT编译Spark的WordCount程序
- stable_sort()与sort
- 201521123002《Java程序设计》第11周学习总结
- 对Java原子类AtomicInteger实现原理的一点总结
- 从零开始学习前端开发 — 2、CSS基础
- WinSCP怎么导入filezilla中的站点？
- Visual Studio Code-批量添加或删除注释行
- 新学了几个python模块，不是很鸡肋。
- [NOIP]2017列队——旋转treap/非旋转treap
- Appium环境搭建python篇（mac系统）
- 2016 ACM/ICPC Asia Regional Qingdao Online 1001 I Count Two Three（打表+二分搜索）
- 首页焦点图myFocus插件
- CSS实现圆角六色渐变自适应按钮
- <OC>OC新特征array literals
- java笔记--多线程基础