常见优化建图技巧
一、线段树优化建图
基本操作：
- \(x\) 向区间 \([l,r]\) 连边
- 区间 \([l,r]\) 向 \(x\) 连边
- 区间 \([l,r]\) 向 区间 \([x,y]\) 连边
建立两棵线段树，一棵从父亲节点向儿子节点连长度为 \(0\) 的边，称为出树；一棵从儿子节点向父亲连长度为 \(0\) 的边，称为入树。并且在出树和入树的相同叶子节点间连长度为 \(0\) 的边
对于操作1，在入树中找到 \(x\) 代表的点，向出树中 \([l,r]\) 覆盖的点连边
对于操作2，在入树中找到 \([l,r]\) 覆盖的点，向出树中 \(x\) 代表的的点连边
对于操作3，在入树中找到 \([l,r]\) 覆盖的点，向虚点连边，虚点再向出树中 \([x,y]\) 覆盖的点连边
这样，我们将边数规模从 \(O(n^2m)\) 降到了 \(O(m\log n)\)，方便我们进行后续操作
CF786B Legacy & P6348 [PA2011] Journeys
板子题
code
// CF786B
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pli pair<long long,int>
#define LL long long
using namespace std;
const int N=100010;
int n,m,s;
vector <pii> g[9*N];
void add(int x,int y,int z)
{
g[x].push_back({y,z});
}
namespace TR
{
#define lc(p) p*2
#define rc(p) p*2+1
int cnt;
struct SegmentTree
{
int id[4*N],pos[N];
void build(int p,int l,int r,int flag)
{
id[p]=++cnt;
if(l==r)
{
pos[l]=cnt;
return;
}
int mid=(l+r)>>1;
build(lc(p),l,mid,flag); build(rc(p),mid+1,r,flag);
if(!flag)
add(id[p],id[lc(p)],0),add(id[p],id[rc(p)],0);
else
add(id[lc(p)],id[p],0),add(id[rc(p)],id[p],0);
}
void addt(int p,int l,int r,int ql,int qr,int u,int w,int flag)
{
if(ql<=l && qr>=r)
{
if(!flag)
add(u,id[p],w);
else
add(id[p],u,w);
return;
}
int mid=(l+r)>>1;
if(ql<=mid)
addt(lc(p),l,mid,ql,qr,u,w,flag);
if(qr>mid)
addt(rc(p),mid+1,r,ql,qr,u,w,flag);
}
}t[2];
}
namespace GR
{
LL d[9*N]; bool v[9*N];
priority_queue <pli> q;
void dijkstra()
{
memset(d,0x3f,sizeof(d));
d[TR::t[1].pos[s]]=0; q.push({0,TR::t[1].pos[s]});
while(q.size())
{
int x=q.top().second; q.pop();
if(v[x])
continue;
v[x]=1;
for(auto vv:g[x])
{
int y=vv.first,z=vv.second;
if(d[y]>d[x]+(LL)z)
d[y]=d[x]+(LL)z,q.push({-d[y],y});
}
}
}
}
int main()
{
using namespace TR;
using namespace GR;
scanf("%d%d%d",&n,&m,&s);
t[0].build(1,1,n,0); t[1].build(1,1,n,1);
for(int i=1; i<=n; i++)
add(t[0].pos[i],t[1].pos[i],0),add(t[1].pos[i],t[0].pos[i],0);
while(m--)
{
int op,u,v,w,l,r;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&u,&v,&w);
add(t[1].pos[u],t[0].pos[v],w);
}
else if(op==2)
{
scanf("%d%d%d%d",&u,&l,&r,&w);
t[0].addt(1,1,n,l,r,t[1].pos[u],w,0);
}
else
{
scanf("%d%d%d%d",&u,&l,&r,&w);
t[1].addt(1,1,n,l,r,t[0].pos[u],w,1);
}
}
dijkstra();
for(int i=1; i<=n; i++)
{
LL res=d[t[0].pos[i]];
if(res>=1e18)
printf("-1 ");
else
printf("%lld ",res);
}
return 0;
}
code
//P6348
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pli pair<long long,int>
#define LL long long
using namespace std;
const int N=500010;
int n,m,s;
vector <pii> g[9*N];
void add(int x,int y,int z)
{
g[x].push_back({y,z});
}
namespace TR
{
#define lc(p) p*2
#define rc(p) p*2+1
int cnt;
struct SegmentTree
{
int id[4*N],pos[N];
void build(int p,int l,int r,int flag)
{
id[p]=++cnt;
if(l==r)
{
pos[l]=cnt;
return;
}
int mid=(l+r)>>1;
build(lc(p),l,mid,flag); build(rc(p),mid+1,r,flag);
if(!flag)
add(id[p],id[lc(p)],0),add(id[p],id[rc(p)],0);
else
add(id[lc(p)],id[p],0),add(id[rc(p)],id[p],0);
}
void addt(int p,int l,int r,int ql,int qr,int u,int w,int flag)
{
if(ql<=l && qr>=r)
{
if(!flag)
add(u,id[p],w);
else
add(id[p],u,w);
return;
}
int mid=(l+r)>>1;
if(ql<=mid)
addt(lc(p),l,mid,ql,qr,u,w,flag);
if(qr>mid)
addt(rc(p),mid+1,r,ql,qr,u,w,flag);
}
}t[2];
}
namespace GR
{
LL d[9*N]; bool v[9*N];
priority_queue <pli> q;
void dijkstra()
{
memset(d,0x3f,sizeof(d));
d[TR::t[1].pos[s]]=0; q.push({0,TR::t[1].pos[s]});
while(q.size())
{
int x=q.top().second; q.pop();
if(v[x])
continue;
v[x]=1;
for(auto vv:g[x])
{
int y=vv.first,z=vv.second;
if(d[y]>d[x]+(LL)z)
d[y]=d[x]+(LL)z,q.push({-d[y],y});
}
}
}
}
int main()
{
using namespace TR;
using namespace GR;
scanf("%d%d%d",&n,&m,&s);
t[0].build(1,1,n,0); t[1].build(1,1,n,1);
for(int i=1; i<=n; i++)
add(t[0].pos[i],t[1].pos[i],0),add(t[1].pos[i],t[0].pos[i],0);
while(m--)
{
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
t[1].addt(1,1,n,a,b,++cnt,1,1);
t[0].addt(1,1,n,c,d,cnt,0,0);
t[1].addt(1,1,n,c,d,++cnt,1,1);
t[0].addt(1,1,n,a,b,cnt,0,0);
}
dijkstra();
for(int i=1; i<=n; i++)
printf("%lld\n",d[t[0].pos[i]]);
return 0;
}