题解：P13901 [CSPro 28] 星际网络
主体思路：
从 the classic problem 中获得启示，我们应该用主席树跑 dijkstra，由于是区间连区间，所以要线段树优化建图，这是线段树建图板子 Legacy ，需要注意的是，因为题意还要返回原星球，所以要建正反两张图，跑
具体实现：
- 我们在主席树维护了
4 个值来维护这个数的二进制表示下的数列，l,r,hs,val ，分别表示左儿子，右儿子，哈希值，二进制下值对10^9+7 取模的余数。 - 我们对于每个点的
dis 数组不再存值，而是存着对应数列的主席树的根，加a\times 2^b 是可以用压位做到更优复杂度的，如这题 整数，但这题不卡，所以可以直接加\log 次，每次加上一个2 的整数次幂，我们可以线段树二分找出\ge b 的第一个0 对应的位置，我们判断一段数列是否为全1 时，可以提前预处理出每一种长度全为1 时的哈希值，直接O(1) 就可以判断，找出这个位置后，就变成了区间赋0 ，单点赋1 ，区间赋0 时，对于完全包含的区间可以直接删除。单次加复杂度O(\log^2) 。 - 优先队列里比较大小时，我们直接线段树二分找到最大的不一样的位置，然后比较
val 就行，比较一段区间是否相同比较它们的val 和hs 值是否相同。 - 因为没有边权，只有点权，每个点最多只会入队
1 次，所以我们可以直接记录点是否入队过，遍历时可以直接判掉，避免过多的比较操作。 - 优先队列比较大小有点慢，这里可以再用普通队列优化，如果松弛时加的点权为
0 时，可以直接加入普通队列，因为不这样优先队列里是有4n+m 个点，加上这个优化，优先队列只有m 个点，快了挺多的。 - 把哈希改成
unsigned int自然溢出，且其他变量一定不要用long long！ - 如果你被卡时间或空间了，可以对着我的代码改下数组大小。
代码实现
#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;
}这题很卡，可能需要多交几发。