首页 > 其他分享 >P9175 [COCI2022-2023#4] Mreža 题解

P9175 [COCI2022-2023#4] Mreža 题解

时间：2024-05-14 20:41:25浏览次数：25  
标签：COCI2022 qr idx int 题解 复杂度 pa Mre define

P9175 [COCI2022-2023#4] Mreža 题解

前言

我发现，有整体二分与主席树的地方总有莫队（不是那个莫队，是那个莫队）。

知识点

（树上）倍增，（树上）莫队，树状数组（“树”含量满满），分块。

题意分析

给定一棵树，每条边有一个权值 \(v\)，以及可以用一个花费 \(c\) 将它变成更大的权值 \(s\)。再给定一些询问，问在总花费不超过一个值 \(e\) 的情况下进行改变，节点 \(a\) 与 \(b\) 之间的边的权值最小值最大为多少。

思路分析

对于每一次询问，我们肯定是节点 \(a\) 与 \(b\) 之间边权最小的边不停更新，直到不能更新。基于这个思路，Subtask 1 已经可以解决了。

但是下一步怎么优化呢？我们可以想到，可以先将原边权离散化，然后根据离散化后的值排序，然后每次查询就变成了在这个数组上从大到小遍历，加上在节点 \(a\) 与 \(b\) 之间路径上的边的权值，直到总和大于 \(e\)，这个过程我们可以用树状数组解决，更新时间复杂度为 \(O(\log_2{n})\)，然后可以树状数组上倍增查询，时间复杂度也为 \(O(\log_2{n})\)（你可以换用分块，这样就可以变成更新时间复杂度为 \(O(1)\)，查询时间复杂度为 \(O(\sqrt{n})\)，总体理论时间复杂度会更加正确）。

然后 Subtask 2 的部分就直接套莫队，也紧接着迎刃而解了。

剩下 Subtask 3，我们在 Subtask 2 的 基础上，用括号序把树上问题转换成序列问题，稍加改进，整个问题就解决了。

最后还有一些细节：

  1. 对于每一次询问，答案上界是节点 \(a\) 与 \(b\) 之间所有更新后的边权最小值，这个可以用树上倍增解决。
  2. 对于每一次询问，当 \(e\) 大于更新节点 \(a\) 与 \(b\) 之间所有边权的总花费，就不需要在树状数组中查询了，否则可能导致错误。
  3. 转换成括号序后，节点 \(a\) 与 \(b\) 为祖孙关系时询问区间要特殊处理。

关于复杂度

空间复杂度上主要瓶颈是倍增数组，为 \(O(n\log_2{n})\)。

那么我们来看时间复杂度。

对于莫队部分，这里简单分析一下：

设 \(S\) 为单块大小，那么块数为 \(O(\frac{n}{S})\) 级别。每次左端点最大移动次数级别为 \(O(S)\)；在左端点在同一块内时，右端点最大移动次数级别为 \(O(n)\)。

所以莫队部分左右端点（指针）移动次数大概为 \(O(qS+\frac{n^2}{S})\)，在 \(S\) 取 \(\frac{n}{\sqrt{q}}\) 的时候最小平衡到 \(O(n\sqrt{q})\)。

然后再分别讨论树状树组与分块的时间复杂度：

  1. 树状树组：单次更新 \(O(\log_2{n})\)，查询 \(O(\log_2{n})\)，总时间复杂度在 \(O(n\log_2{n}\sqrt{q}+q\log_2{n})\) 左右；
  2. 分块：单次更新 \(O(1)\)，查询 \(O(\sqrt{n})\)，总时间复杂度在 \(O(n\sqrt{q}+q\sqrt{n})\) 左右。

首先分块肯定没问题，但是树状数组呢，它的理论总时间复杂度好像不太行啊？

我们注意到莫队这类题目的时间复杂度一般都是讨论最坏情况，所以基本都是跑不满的，再加之这还是个树上莫队，真的要卡它也很难。就算是链，我们在块长不一样的情况下，运行的情况也是不一样的。如果还不够的话，我们在规定根以及遍历子节点的时候都加上随机化，那么基本是卡不掉了（喜欢快读快写也可以加）。

现在看实测，最长的点时间也不超过 1.5 s，而时限是 5 s，说明 COCI 出题人还有点良心 完全可以。

CODE

  1. 树状树组：（去掉了快读，不是上面那个）用时 2.45 s，内存 33.40 MB，单个测试点最长时间为 1.57 s。

    #include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e5+10,lN=17,lV=lN+1;
int n,Q,idx,Bl;
int b[N],dl[N],dr[N],id[N<<1],pa[N],ans[N],dep[N],dfn[N<<1],siz[N],son[N];
int fa[N][lV],mi[N][lV];
ll sum;
struct edge{
	int u,v,w,c,s;
	void Scan(){
		cin>>u>>v>>w>>c>>s;
	}
}e[N];
struct Query{
	int l,r,idx;ll w;
	friend bool operator <(Query a,Query b){
		return id[a.l]^id[b.l]?a.l<b.l:(id[a.l]&1)^(a.r>b.r);
	}
}qr[N];
struct BIT{
#define lowbit(a) ((a)&-(a))
	ll c[N];
	void Update(int x,int v){
		if(x<=0)return;
		for(int i=x;i<=b[0];i+=lowbit(i))c[i]+=v;
	}
	int Bound(ll x){
		ll sum=0;int ans=0;
		DOR(i,lN,0)if(ans+(1<<i)<=b[0]&&sum+c[ans+(1<<i)]<x)sum+=c[ans+=1<<i];
		return ans+1;
	}
#undef lowbit
}B;
struct CFS{
	int tot,h[N],v[N<<1],nxt[N<<1];
	void att(int U,int V){
		v[++tot]=V,nxt[tot]=h[U],h[U]=tot;
	}
	void con(int U,int V){
		att(U,V),att(V,U);
	}
}g;
void Build(int u){
	dep[u]=dep[fa[u][0]]+1,mi[u][0]=e[pa[u]].s,siz[u]=1;
	FOR(i,1,lN)fa[u][i]=fa[fa[u][i-1]][i-1],mi[u][i]=min(mi[u][i-1],mi[fa[u][i-1]][i-1]);
	EDGE(g,i,u,v)if(v^fa[u][0])
		pa[v]=i+1>>1,fa[v][0]=u,Build(v),siz[u]+=siz[v],son[u]=(siz[son[u]]>siz[v]?son[u]:v);
}
void Divide(int u){
	dfn[dl[u]=++idx]=u;
	if(son[u])Divide(son[u]);
	EDGE(g,i,u,v)if(son[u]!=v&&fa[u][0]!=v)Divide(v);
	dfn[dr[u]=++idx]=u;
}
int Lca(int u,int v){
	if(dep[v]<dep[u])swap(u,v);
	DOR(i,lN,0)if(dep[v]-dep[u]&1<<i)v=fa[v][i];
	if(u==v)return u;
	DOR(i,lN,0)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[v][0];
}
int Query(int u,int pa){
	int ans=INF;
	DOR(i,lN,0)if(dep[fa[u][i]]>=dep[pa])tomin(ans,mi[u][i]),u=fa[u][i];
	return ans;
}
bool vis[N];
void Update(int x){
	if(x>1)sum+=(vis[x]?-1:1)*e[pa[x]].c,B.Update(e[pa[x]].w,(vis[x]?-1:1)*e[pa[x]].c),vis[x]^=1;
}
signed main(){
	cin>>n;
	FOR(i,1,n-1)e[i].Scan(),g.con(e[i].u,e[i].v),b[i]=e[i].w;
	sort(b+1,b+n),b[0]=unique(b+1,b+n)-b-1;
	FOR(i,1,n-1)e[i].w=lower_bound(b+1,b+b[0]+1,e[i].w)-b;
	cin>>Q,Build(1),Divide(1),Bl=ceil(2.0*n/sqrt(Q));
	FOR(i,1,n<<1)id[i]=(i-1)/Bl+1;
	FOR(i,1,Q){
		int u,v,pa;cin>>u>>v>>qr[i].w,pa=Lca(u,v);
		if(dl[u]>dl[v])swap(u,v);
		qr[i].l=pa==u?dl[u]+1:dr[u],qr[i].r=dl[v],ans[qr[i].idx=i]=min(Query(u,pa),Query(v,pa));
	}
	sort(qr+1,qr+Q+1);
	int l=1,r=0;
	FOR(i,1,Q){
		while(r<qr[i].r)Update(dfn[++r]);
		while(l>qr[i].l)Update(dfn[--l]);
		while(r>qr[i].r)Update(dfn[r--]);
		while(l<qr[i].l)Update(dfn[l++]);
		if(qr[i].w<sum)tomin(ans[qr[i].idx],b[B.Bound(qr[i].w+1)]);
	}
	FOR(i,1,Q)cout<<ans[i]<<endl;
	return 0;
}

  2. 分块：（卑微的记录.）用时 1.15 s，内存 33.73 MB，单个测试点最长时间为 688 ms。

    #include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=1e5+10,lN=17,lV=lN+1,sN=340+10;
bool vis[N];
int n,Q,idx,Bl;
int b[N],dl[N],dr[N],id[N<<1],pa[N],ans[N],dep[N],dfn[N<<1],siz[N],son[N];
int fa[N][lV],mi[N][lV];
ll sum;
struct edge{
	int u,v,w,c,s;
	void Scan(){
		cin>>u>>v>>w>>c>>s;
	}
}e[N];
struct Query{
	int l,r,idx;ll w;
	friend bool operator <(Query a,Query b){
		return id[a.l]^id[b.l]?a.l<b.l:(id[a.l]&1)^(a.r>b.r);
	}
}qr[N];
struct Block{
	int Bl,Bn;
	int st[sN],en[sN],id[N];
	ll Sum[sN],sum[N];
	void Init(int n){
		Bl=sqrt(n),Bn=(n-1)/Bl+1;
		FOR(i,1,Bn){
			st[i]=en[i-1]+1,en[i]=min(n,st[i]+Bl-1);
			FOR(j,st[i],en[i])id[j]=i;
		}
	}
	void Update(int x,int d){
		sum[x]+=d,Sum[id[x]]+=d;
	}
	int Query(ll x){
		int Idx=0,idx=0;ll s=0;
		for(Idx=0;Idx<=Bn;s+=Sum[Idx],++Idx)if(s+Sum[Idx]>x)break;
		for(idx=st[Idx];idx<=en[Idx];s+=sum[idx],++idx)if(s+sum[idx]>x)break;
		return idx;
	}
}B;
struct CFS{
	int tot,h[N],v[N<<1],nxt[N<<1];
	void att(int U,int V){
		v[++tot]=V,nxt[tot]=h[U],h[U]=tot;
	}
	void con(int U,int V){
		att(U,V),att(V,U);
	}
}g;
void Build(int u){
	dep[u]=dep[fa[u][0]]+1,mi[u][0]=e[pa[u]].s,siz[u]=1;
	FOR(i,1,lN)fa[u][i]=fa[fa[u][i-1]][i-1],mi[u][i]=min(mi[u][i-1],mi[fa[u][i-1]][i-1]);
	EDGE(g,i,u,v)if(v^fa[u][0])
		pa[v]=i+1>>1,fa[v][0]=u,Build(v),siz[u]+=siz[v],son[u]=(siz[son[u]]>siz[v]?son[u]:v);
}
void Divide(int u){
	dfn[dl[u]=++idx]=u;
	if(son[u])Divide(son[u]);
	EDGE(g,i,u,v)if(son[u]!=v&&fa[u][0]!=v)Divide(v);
	dfn[dr[u]=++idx]=u;
}
int Lca(int u,int v){
	if(dep[v]<dep[u])swap(u,v);
	DOR(i,lN,0)if(dep[v]-dep[u]&1<<i)v=fa[v][i];
	if(u==v)return u;
	DOR(i,lN,0)if(fa[u][i]^fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[v][0];
}
int Query(int u,int pa){
	int ans=INF;
	DOR(i,lN,0)if(dep[fa[u][i]]>=dep[pa])tomin(ans,mi[u][i]),u=fa[u][i];
	return ans;
}
void Update(int x){
	if(x>1)sum+=(vis[x]?-1:1)*e[pa[x]].c,B.Update(e[pa[x]].w,(vis[x]?-1:1)*e[pa[x]].c),vis[x]^=1;
}
signed main(){
	cin>>n;
	FOR(i,1,n-1)e[i].Scan(),g.con(e[i].u,e[i].v),b[i]=e[i].w;
	sort(b+1,b+n),b[0]=unique(b+1,b+n)-b-1,B.Init(b[0]);
	FOR(i,1,n-1)e[i].w=lower_bound(b+1,b+b[0]+1,e[i].w)-b;
	cin>>Q,Build(1),Divide(1),Bl=ceil(2.0*n/sqrt(Q));
	FOR(i,1,n<<1)id[i]=(i-1)/Bl+1;
	FOR(i,1,Q){
		int u,v,pa;cin>>u>>v>>qr[i].w,pa=Lca(u,v);
		if(dl[u]>dl[v])swap(u,v);
		qr[i].l=pa==u?dl[u]+1:dr[u],qr[i].r=dl[v],ans[qr[i].idx=i]=min(Query(u,pa),Query(v,pa));
	}
	sort(qr+1,qr+Q+1);
	int l=1,r=0;
	FOR(i,1,Q){
		while(r<qr[i].r)Update(dfn[++r]);
		while(l>qr[i].l)Update(dfn[--l]);
		while(r>qr[i].r)Update(dfn[r--]);
		while(l<qr[i].l)Update(dfn[l++]);
		if(qr[i].w<sum)tomin(ans[qr[i].idx],b[B.Query(qr[i].w)]);
	}
	FOR(i,1,Q)cout<<ans[i]<<endl;
	return 0;
}

小小吐槽一下

我考试的时候想到了树状数组的做法，但是倍增写错了，然后就只有 Subtask 2 的分数了……（欲哭无泪）

后记

链接是不是点不进去啊？哈哈哈。 （皮一下很开心）

标签：COCI2022,qr,idx,int,题解,复杂度,pa,Mre,define
From： https://www.cnblogs.com/Cat-litter/p/18192221

相关文章

  • Little Pony and Lord Tirek 题解
    LittlePonyandLordTirek题解\(\texttt{ProblemLink}\)题目大意给定长度为\(n\)的序列，第\(i\)个数有三个值：\(s_i,m_i,r_i\)，每秒对于每个数执行\(s_i\leftarrow\min\{s_i+r_i,m_i\}\)。有\(m\)个查询，每次查询三个值：\(t,l,r\)查询时刻\(t\)，\([l,......
  • [H&NCTF] maybe_xor题解
    maybe_xor感觉这道逆向题与其说是考逆向水平，倒不如说是考编写脚本的能力首先题目给了个远程地址，nc连接会回显ELF:接一串base64编码的东东，解码后发现是ELF文件。用IDA打开发现是从数据段读取24个字节到栈上并进行异或，每个字节异或的值都不同，但异或后的结果不会写回栈程序的目......
  • [题解] Flipping Game
    题目描述有n盏灯，每个灯有开和关两种状态。每按一次灯会变成相反的状态。给定灯初始的开关状态和结束的开关状态，若操作k轮，每轮要按m个不同的灯，问有多少种方法使灯由初始状态变到结束状态。题解需注意每轮要按不同的灯，若无这个条件，暴力计算组合数即可。要操作多轮，且每轮按灯的......
  • 题解：SP10232 AMR11E - Distinct Primes
    前话这咋人名都和HP一模一样了，SPOJ出题人里是不是全是哈迷啊。思路非常直观的一个思路：从前往后枚举每一个数，看是否满足条件，输出满足条件的第一个。CODE#include<bits/stdc++.h>usingnamespacestd;boolis(intn){//判断质数if(n<2)return0;for(inti=2;i<......
  • 题解：CF1337A Ichihime and Triangle
    看到大佬们基本都是直接输出\(b\)\(c\)\(c\)了事儿，一身反骨有其它构造方法的我表示不服，遂作此篇。众所周知，两边之和大于第三边，所以，如果\(b+c>d\)，那么\(b\)、\(c\)、\(d\)就是正确的。那如果不满足呢？在题目条件下\(b+c>b+c-1\)，那么这一组就是合理的。分别验......
  • NOIP真题题解
    2001T4Car的旅行路线ybtluogu建图+最短路1.建图时细节较多已知三点求第四点的坐标勾股定理判断斜边2.最短路时多起点多终点2013D1T3货车运输ybtluogu最大生成树+倍增LCA答案的边一定在最大生成树上将原图建出最大生成树在树上使用倍增LCA提取路径2014D2T2寻......
  • 5.13 模拟赛题解（没写完）
    T1P4304[TJOI2013]攻击装置快进到HZOI2023超越HZOI2020（人均场切了紫）考虑将棋盘黑白染色成这个样子容易发现相同颜色的点直接一定没有冲突，满足二分图的性质，需要求出最小点覆盖，所以直接按冲突建好双向边，从\(1\)到\(n^2\)节点跑最大匹配即可。设求出的最大匹配为\(......
  • HydroOJ 从入门到入土（19）导入题解和标程、题目数据统计(>=4.12.0)
    题解和std可以导入了，导出还会远吗？目录一、导入题解和标程1.目录结构2.测试结果3.第二次测试题目结构如下：测试结果：4.总结：关于题解：关于标程（std）：去除.DS_Store的解决方法二、题目数据统计1.范围2.筛选选项3.无关紧要的小bug一、导入题解和标程新版本更新了这个功能，方......
  • THUSC总结PART1-比赛总结/题解
    第一次参加\(THU\)的营,战绩惨不忍睹.D1T1给出\(d\),\(n_1\cdotsn_d\),\(l\),求\[\sum_{i_1=0}^{n_1-1}\sum_{2_1=0}^{n_2-1}\cdots\sum_{i_d=0}^{n_d-1}\max(0,(i_1\oplusi_2\oplus\cdotsi_d)-l)\]其中\(d<=10\),\(n_i<=1e18\),\......
  • 【问题解决】java.lang.NoSuchMethodError错误
    问题现象近期本人负责的一个SpringBoot模块出现了java.lang.NoSuchMethodError报错，问题情况如下：A类提供了setJumpType(Stringtype)，B类调用A类的setJumpType(Stringtype)报错java.lang.NoSuchMethodError:com.xxx.A.setJumpType(Ljava/lang/String;)V在之前的发版的程序中，B......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99