嗨,我正在尝试为 rmq-ing 实现 2D 范围树,这是我的代码,我认为它不够高效,有什么我可以做的优化。
ls 包含在每个节点上排序的 y 列表
rt 包含一个段树
p.fi.fi 包含 x 坐标
p.fi.se 包含 y 坐标
p.se 包含点的 id
loc 包含每个 id 的 x 节点和 y 节点
vector<pii> ls[400005];
vector<int> rt[400005];
pair<pii,int> p[100005];
vector<pii> loc[100005];
inline void merge(int id,vector<pii> &res,vector<pii> &a,vector<pii> &b)
{
int la = 0;
int lb = 0;
int sa = SIZE(a);
int sb = SIZE(b);
while(la < sa || lb < sb)
{
if (la >= sa) {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
else if (lb >= sb) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
else
{
if (a[la] < b[lb]) {res.pb(a[la]);loc[a[la].se].pb(mp(id,SIZE(res)-1));la++;}
else {res.pb(b[lb]);loc[b[lb].se].pb(mp(id,SIZE(res)-1));lb++;}
}
}
}
inline void build_x(int n,int l,int r)
{
if (l == r)
{
ls[n].clear();
ls[n].pb(mp(p[l].fi.se,p[l].se));
rt[n].assign(SIZE(ls[n])<<2,0);
loc[p[l].se].pb(mp(n,0));
return;
}
int m = (l+r)>>1;
build_x((n<<1),l,m);
build_x((n<<1)+1,m+1,r);
ls[n].clear();
merge(n,ls[n],ls[(n<<1)],ls[(n<<1)+1]);
rt[n].assign(SIZE(ls[n])<<2,0);
}
inline int query_y(int nx,int n,int l,int r,int ly,int ry)
{
if (ly > ls[nx][r].fi || ry < ls[nx][l].fi) return 0;
if (ly <= ls[nx][l].fi && ls[nx][r].fi <= ry)
{
return rt[nx][n];
}
int res = 0;
int m = (l+r)>>1;
if (ly <= ls[nx][m].fi) MAX(res,query_y(nx,(n<<1),l,m,ly,min(ls[nx][m].fi,ry)));
if (ls[nx][m+1].fi <= ry) MAX(res,query_y(nx,(n<<1)+1,m+1,r,max(ls[nx][m+1].fi,ly),ry));
return res;
}
inline int query_x(int n,int l,int r,int lx,int rx,int ly,int ry)
{
if (lx > p[r].fi.fi || rx < p[l].fi.fi) return 0;
if (lx <= p[l].fi.fi && p[r].fi.fi <= rx)
{
return query_y(n,1,0,SIZE(ls[n])-1,ly,ry);
}
int res = 0;
int m = (l+r)>>1;
if (lx <= p[m].fi.fi) MAX(res,query_x((n<<1),l,m,lx,min(p[m].fi.fi,rx),ly,ry));
if (p[m+1].fi.fi <= rx) MAX(res,query_x((n<<1)+1,m+1,r,max(p[m+1].fi.fi,lx),rx,ly,ry));
return res;
}
int nx;
inline void update_y(int n,int l,int r,int fy,int v)
{
if (l == r)
{
MAX(rt[nx][n],v);
return;
}
int m = (l+r)>>1;
if (fy <= m) update_y((n<<1),l,m,fy,v);
else update_y((n<<1)+1,m+1,r,fy,v);
rt[nx][n] = max(rt[nx][(n<<1)],rt[nx][(n<<1)+1]);
}
如果代码是一团糟,我很抱歉,因为这是我第一次实现范围树
我当前的实现运行了大约 4 秒,但我需要它运行不到 3 秒,这是我的完整 实现
谢谢 :)