专栏文章

题解：P13901 [CSPro 28] 星际网络

OOld_tree
P13901题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@min7p2au
此快照首次捕获于
2025/12/01 21:55
3 个月前
此快照最后确认于
2025/12/01 21:55
3 个月前
查看原文

主体思路：

从 the classic problem 中获得启示，我们应该用主席树跑 dijkstra，由于是区间连区间，所以要线段树优化建图，这是线段树建图板子 Legacy ，需要注意的是，因为题意还要返回原星球，所以要建正反两张图，跑 22 遍 dijkstra！

具体实现：

  • 我们在主席树维护了 44 个值来维护这个数的二进制表示下的数列，l,r,hs,vall,r,hs,val，分别表示左儿子，右儿子，哈希值，二进制下值对 109+710^9+7 取模的余数。
  • 我们对于每个点的 disdis 数组不再存值，而是存着对应数列的主席树的根，加 a×2ba\times 2^b 是可以用压位做到更优复杂度的，如这题 整数，但这题不卡，所以可以直接加 log⁡\log 次，每次加上一个 22 的整数次幂，我们可以线段树二分找出 ≥b\ge b 的第一个 00 对应的位置，我们判断一段数列是否为全 11 时，可以提前预处理出每一种长度全为 11 时的哈希值，直接 O(1)O(1) 就可以判断，找出这个位置后，就变成了区间赋 00，单点赋 11，区间赋 00 时，对于完全包含的区间可以直接删除。单次加复杂度 O(log⁡2)O(\log^2)。
  • 优先队列里比较大小时，我们直接线段树二分找到最大的不一样的位置，然后比较 valval 就行，比较一段区间是否相同比较它们的 valval 和 hshs 值是否相同。
  • 因为没有边权，只有点权，每个点最多只会入队 11 次，所以我们可以直接记录点是否入队过，遍历时可以直接判掉，避免过多的比较操作。
  • 优先队列比较大小有点慢，这里可以再用普通队列优化，如果松弛时加的点权为 00 时，可以直接加入普通队列，因为不这样优先队列里是有 4n+m4n+m 个点，加上这个优化，优先队列只有 mm 个点，快了挺多的。
  • 把哈希改成 unsigned int 自然溢出，且其他变量一定不要用 long long！
  • 如果你被卡时间或空间了，可以对着我的代码改下数组大小。

代码实现

CPP
#include<bits/stdc++.h>
#pragma GGC optimize(3)
#define rep(x,y,z) for(int x=y;x<=z;++x)
#define per(x,y,z) for(int x=y;x>=z;--x)
#define qwq cout<<'\n'
#define exq exit(0)
#define cmin(x,y) x=min(x,y)
#define cmax(x,y) x=max(x,y)
#define pii pair<int,int>
#define pb push_back
#define emb push_back
#include<queue>
//#define int long long
using namespace std;
mt19937 rnd(time(0));
void IOS() {
	ios::sync_with_stdio(0);
	cin.tie(nullptr);
}
const int N=1e5+57;
const int ms=1e6+66;
const int mod=1e9+7;
//using ll=long long;
int n;
int m;
int k2[N];
unsigned int k131[N];
unsigned int khs[N];
struct seg{
	int l,r;
}tr[N<<2];
int rot1,rot2;
vector<int> E[ms];
vector<int> EE[ms];
int tot1;
int g[2][N];
void add(int u,int v){E[u].emb(v);}
void _add(int u,int v){EE[u].emb(v);}
void build(int &now,int l,int r,int opt){
	if(!now) now=++tot1;
	if(l==r){
		g[opt][l]=now;
		return;
	}
	int mid=(l+r)>>1;
	build(tr[now].l,l,mid,opt);
	build(tr[now].r,mid+1,r,opt);
	if(!opt){
		add(now,tr[now].l);
		add(now,tr[now].r);
		_add(now,tr[now].l);
		_add(now,tr[now].r);
	}
	else{
		add(tr[now].l,now);
		add(tr[now].r,now);
		_add(tr[now].l,now);
		_add(tr[now].r,now);
	}
}
vector<int> G;
void ask(int now,int l,int r,int L,int R){
	if(L>=l&&R<=r){
		G.emb(now);
		return;
	}
	int mid=(L+R)>>1;
	if(l<=mid) ask(tr[now].l,l,r,L,mid);
	if(r> mid) ask(tr[now].r,l,r,mid+1,R);
}
int dis[ms];
int tot2;
struct segm{
	int l,r;
	unsigned int hs;
	int val;
}t[N*414];
void _build(int &now,int l,int r){
	now=++tot2;
	if(l==r) return;
	int mid=(l+r)>>1;
	_build(t[now].l,l,mid);
	_build(t[now].r,mid+1,r);
}
int rtg;
bool che(int x,int y){
	if(t[x].val!=t[y].val) return false;
	if(t[x].hs!=t[y].hs) return false;
	return true;
}
bool segment_ef(int x,int y,int L,int R){
	if(L==R) return t[x].val<=t[y].val;
	int mid=(L+R)>>1;
	if(che(t[x].r,t[y].r)) return segment_ef(t[x].l,t[y].l,L,mid);
	return segment_ef(t[x].r,t[y].r,mid+1,R);
}
struct adsg{
	int x;
	bool operator < (const adsg&it) const {
		if(che(dis[x],dis[it.x])) return 1;
		return segment_ef(dis[x],dis[it.x],1,100055); // x<y; 
	}
	bool operator > (const adsg&it) const {
		if(che(dis[x],dis[it.x])) return 1;
		return !segment_ef(dis[x],dis[it.x],1,100055);
	}
};
priority_queue<adsg,vector<adsg>,greater<adsg> > qu;
bool vos[ms];
int zha[ms];
int zhb[ms];
int rmx;
int Lmx;
int Rmx;
void query(int now,int lim,int L,int R){
	if(Lmx) return;
	if(L>=lim){
		if(t[now].hs!=khs[R-L]){
			rmx=now;
			Lmx=L;
			Rmx=R;
		}
		return;
	}
	int mid=(L+R)>>1;
	if(lim<=mid) query(t[now].l,lim,L,mid);
	query(t[now].r,lim,mid+1,R);
}
int seg_ef(int now,int L,int R){
	if(L==R) return L;
	int mid=(L+R)>>1;
	if(t[t[now].l].hs!=khs[mid-L]) return seg_ef(t[now].l,L,mid);
	return seg_ef(t[now].r,mid+1,R);
}
void renew(int now,int L,int R){
	int mid=(L+R)>>1;
	t[now].val=(long long)t[t[now].r].val*k2[mid-L+1]%mod;
	t[now].val=(t[now].val+t[t[now].l].val)%mod;
	t[now].hs=t[t[now].r].hs;
	t[now].hs*=k131[mid-L+1];
	t[now].hs+=t[t[now].l].hs;
}
int chan1(int now,int pos,int L,int R){
	int iow=++tot2;
	t[iow]=t[now];
	if(L==R){
		t[iow].val=1;
		t[iow].hs=1;
		return iow;
	}
	int mid=(L+R)>>1;
	if(pos<=mid) t[iow].l=chan1(t[iow].l,pos,L,mid);
	else t[iow].r=chan1(t[iow].r,pos,mid+1,R);
	renew(iow,L,R);
	return iow;
}
int chan0(int now,int l,int r,int L,int R){
	if(L>=l&&R<=r) return 0;
	int iow=++tot2;
	t[iow]=t[now];
	int mid=(L+R)>>1;
	if(l<=mid) t[iow].l=chan0(t[iow].l,l,r,L,mid);
	if(r> mid) t[iow].r=chan0(t[iow].r,l,r,mid+1,R);
	renew(iow,L,R);
	return iow;
}
void solve(int x,int ax,int bx){
	int b;
	while(ax){
		int _x=(ax&-ax);
		b=log2(_x)+bx+1;
		ax-=_x;
		rmx=0;
		Lmx=0;
		query(dis[x],b,1,100055);
		int pos=seg_ef(rmx,Lmx,Rmx);
		dis[x]=chan1(dis[x],pos,1,100055);
		if(pos!=b) dis[x]=chan0(dis[x],b,pos-1,1,100055);
	}
}
long long answer[N];
queue<int> qqu;
main(){
	IOS();
	cin>>n>>m;
	k2[0]=1;
	k131[0]=1;
	khs[0]=1;
	rep(i,1,100055){
		k2[i]=(long long)k2[i-1]*2%mod;
		k131[i]=(long long)k131[i-1]*131;
		khs[i]=khs[i-1]+k131[i];
	}
	build(rot1,1,n,0);
	build(rot2,1,n,1);
	rep(i,1,n){
		add(g[0][i],g[1][i]);
		add(g[1][i],g[0][i]);
		_add(g[0][i],g[1][i]);
		_add(g[1][i],g[0][i]);
	}
	rep(i,1,m){
		int _l,_r,l_,r_,_a,_b;
		cin>>_l>>_r>>l_>>r_>>_a>>_b;
		int ju=++tot1;
		zha[tot1]=_a;
		zhb[tot1]=_b;
		G.clear();
		ask(rot2,_l,_r,1,n);
		for(int v:G) add(v,ju);
		G.clear();
		ask(rot1,l_,r_,1,n);
		for(int v:G) add(ju,v);
		
		
		ju=++tot1;
		zha[tot1]=_a;
		zhb[tot1]=_b;
		G.clear();
		ask(rot2,l_,r_,1,n);
		for(int v:G) _add(v,ju);
		G.clear();
		ask(rot1,_l,_r,1,n);
		for(int v:G) _add(ju,v);
	}
	_build(dis[g[0][1]],1,100055);
	qu.push({g[0][1]});
	while(!qu.empty()){
		int x=qu.top().x;
		vos[x]=true;
		qu.pop();
		for(int v:E[x]){
			if(vos[v]) continue;
			vos[v]=true;
			dis[v]=++tot2;
			t[tot2]=t[dis[x]];
			if(zha[v]) solve(v,zha[v],zhb[v]);
			qu.push({v});
		}
	}
	rep(i,2,n){
		int v=g[0][i];
		if(!vos[v]) answer[i]=-1;
		else answer[i]=t[dis[v]].val;
	}
	rep(i,1,tot1) vos[i]=0;
	tot2=0;
	_build(dis[g[0][1]],1,100055);
	qu.push({g[0][1]});
	while(!qu.empty()){
		int _x=qu.top().x;
		qu.pop();
		qqu.push(_x);
		while(!qqu.empty()){
			int x=qqu.front();
			vos[x]=true;
			qqu.pop();
			for(int v:EE[x]){
				if(vos[v]) continue;
				vos[v]=true;
				dis[v]=++tot2;
				t[tot2]=t[dis[x]];
				if(zha[v]){
					solve(v,zha[v],zhb[v]);
					qu.push({v});
				}
				else qqu.push(v);
			}
		}
	}
	rep(i,2,n){
		int v=g[0][i];
		if(!vos[v]||answer[i]==-1) answer[i]=-1;
		else (answer[i]+=t[dis[v]].val)%=mod;
	}
	rep(i,2,n) cout<<answer[i]<<' ';
	return 0;
}
这题很卡，可能需要多交几发。

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...