[NOI2019]弹跳(KD-Tree/四分树/线段树套平衡树优化建图+Dijkstra)

本题可以用的方法很多，除去以下三种我所知道的就还有至少三种。

方法一：类似线段树优化建图，将一个平面等分成四份（若只有一行或一列则等分成两份），然后跑Dijkstra即可。建树是$O(n\log n)$的，单次连边是$O(n\log^2 n)$的。

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 #define For(i,x) for (int i=h[x],k; i; i=nxt[i])

 using namespace std;

 const int N=,M=;

 struct E{ int w,l,r,u,d; }p[N];

 struct P{ int u,d; };

 vector<int>G[N];

 int n,m,W,H,now,dis,x,y,cnt,rt,tot,h[N],to[M],nxt[M],w[M],vis[N],d[N],ch[N][];

 bool operator <(P x,P y){ return x.d>y.d; }

 priority_queue<P>Q;

 void add(int x,int y,int z){ to[++cnt]=y; nxt[cnt]=h[x]; w[cnt]=z; h[x]=cnt; }

 void ins(int fa,int &k,int xl,int xr,int yl,int yr,int x,int y){

     if (x<xl||x>xr||y<yl||y>yr) return;

     if (!k) k=++tot;

     if (k!=rt) add(fa+n,k+n,);

     if (xl==xr&&yl==yr){ add(k+n,now,); return; }

     int xm=(xl+xr)>>,ym=(yl+yr)>>;

     ins(k,ch[k][],xl,xm,yl,ym,x,y);

     ins(k,ch[k][],xl,xm,ym+,yr,x,y);

     ins(k,ch[k][],xm+,xr,yl,ym,x,y);

     ins(k,ch[k][],xm+,xr,ym+,yr,x,y);

 }

 void link(int k,int xl,int xr,int yl,int yr,int xL,int xR,int yL,int yR){

     if (!k||xR<xl||xL>xr||yR<yl||yL>yr||d[k+n]<=dis) return;

     if (xl>=xL&&xr<=xR&&yl>=yL&&yr<=yR){ d[k+n]=dis; Q.push((P){k+n,d[k+n]}); return; }

     int xm=(xl+xr)>>,ym=(yl+yr)>>;

     link(ch[k][],xl,xm,yl,ym,xL,xR,yL,yR);

     link(ch[k][],xl,xm,ym+,yr,xL,xR,yL,yR);

     link(ch[k][],xm+,xr,yl,ym,xL,xR,yL,yR);

     link(ch[k][],xm+,xr,ym+,yr,xL,xR,yL,yR);

 }

 int main(){

     freopen("jump.in","r",stdin);

     freopen("jump.out","w",stdout);

     scanf("%d%d%d%d",&n,&m,&W,&H);

     rep(i,,n) scanf("%d%d",&x,&y),now=i,ins(,rt,,W,,H,x,y);

     rep(i,,m) scanf("%d%d%d%d%d%d",&now,&p[i].w,&p[i].l,&p[i].r,&p[i].u,&p[i].d),G[now].push_back(i);

     memset(d,,sizeof(d)); d[]=; Q.push((P){,});

     while (!Q.empty()){

         int u=Q.top().u; Q.pop();

         if (vis[u]) continue; vis[u]=;

         for (int i=;i<(int)G[u].size();i++)

             x=G[u][i],dis=d[u]+p[x].w,link(rt,,W,,H,p[x].l,p[x].r,p[x].u,p[x].d);

         For(i,u) if (d[k=to[i]]>d[u]+w[i]) Q.push((P){k,d[k]=d[u]+w[i]});

     }

     rep(i,,n) printf("%d\n",d[i]);

     return ;

 }

四分树

方法二：一维使用线段树，另一维用set维护这行中的每个点。注意到在Dijikstra时，一条边至多被松弛一次，即一个矩阵至多被访问一次，所以访问并更新一个点之后就可以直接将其删去，复杂度$O(n\log^2 n+m\log m)$。

 #include<set>

 #include<queue>

 #include<vector>

 #include<cstdio>

 #include<algorithm>

 #define ls (x<<1)

 #define rs (ls|1)

 #define lson ls,l,mid

 #define rson rs,mid+1,r

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 typedef pair<int, int>pii;

 typedef multiset<pii>::iterator iter;

 const int N=,M=,S=(<<)+;

 int n,m,W,H,x,p,id,yp[N],vis[N],dis[N],h[N],nxt[M],val[M],L[M],R[M],D[M],U[M];

 multiset<pii>st[S];

 priority_queue<pii> Q;

 void ins(int x,int l,int r,int k,int id){

     st[x].insert(pii(yp[id],id));

     if (l==r) return;

     int mid=(l+r)>>;

     if (k<=mid) ins(lson,k,id); else ins(rson,k,id);

 }

 void del(int x,int l,int r,int id,int d){

     if (r<L[id] || R[id]<l) return;

     if (L[id]<=l && r<=R[id]){

         iter it=st[x].lower_bound(pii(D[id],)),tmp;

         while (it!=st[x].end() && it->first<=U[id]){

             int u=it->second;

             if (!vis[u]){

                 vis[u]=; dis[u]=d;

                 for (int j=h[u]; j; j=nxt[j]) Q.push(pii(-d-val[j],j));

             }

             tmp=it; it++; st[x].erase(tmp);

         }

         return;

     }

     int mid=(l+r)>>; del(lson,id,d); del(rson,id,d);

 }

 int main(){

     freopen("jump.in","r",stdin);

     freopen("jump.out","w",stdout);

     scanf("%d%d%d%d",&n,&m,&W,&H);

     rep(i,,n) scanf("%d%d",&x,&yp[i]),ins(,,W,x,i);

     rep(i,,m) scanf("%d%d%d%d%d%d",&p,&val[i],&L[i],&R[i],&D[i],&U[i]),nxt[i]=h[p],h[p]=i;

     dis[]=; vis[]=;

     for (int i=h[]; i; i=nxt[i]) Q.push(pii(-val[i],i));

     while (!Q.empty()){

         pii ed=Q.top(); Q.pop();

         int dis=-ed.first; id=ed.second; del(,,W,id,dis);

     }

     rep(i,,n) printf("%d\n",dis[i]);

     return ;

 }

线段树套set

方法三：类似方法二地，用KD-Tree优化建图，树上每个点新建一个新点，每个叶子连向这个坐标对应的点。同样在Dijkstra时，每次访问并更新时删除这个点。复杂度可能可以用一些做到$O(n\log^2 n)$，但这里没用。

 #include<set>

 #include<queue>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=,inf=0x3f3f3f3f;

 int n,m,w,h,rt,D,cnt,id[N*],dis[N*],vis[N*];

 int nu,nt,xl,xr,yl,yr,nd[N*],len;

 struct data{

     int nt,xl,xr,yl,yr;

     bool operator>(const data &b)const{ return nt>b.nt; }

 };

 vector<data>f[N*];

 priority_queue<data,vector<data>,greater<data> >Q;

 struct P{

     int x[],id;

     bool operator<(const P&b)const{ return x[D]!=b.x[D] ? x[D]<b.x[D] : x[D^]<b.x[D^]; }

 }p[N];

 struct Tr{ int mx[],mn[],lc,rc,siz; }t[N*];

 void upd(int u){

     t[u].mn[]=t[u].mn[]=inf;

     t[u].mx[]=t[u].mx[]=-inf;

     t[u].siz=; int v=t[u].lc;

     if (v){

         t[u].siz+=t[v].siz;

         t[u].mx[]=max(t[u].mx[],t[v].mx[]),t[u].mx[]=max(t[u].mx[],t[v].mx[]);

         t[u].mn[]=min(t[u].mn[],t[v].mn[]),t[u].mn[]=min(t[u].mn[],t[v].mn[]);

     }

     v=t[u].rc;

     if (v){

         t[u].siz+=t[v].siz;

         t[u].mx[]=max(t[u].mx[],t[v].mx[]),t[u].mx[]=max(t[u].mx[],t[v].mx[]);

         t[u].mn[]=min(t[u].mn[],t[v].mn[]),t[u].mn[]=min(t[u].mn[],t[v].mn[]);

     }

 }

 int bud(int l,int r,int wd){

     int u=++cnt,mid=(l+r)>>;t[u].siz=;

     if (l==r){

         id[u]=p[l].id;

         t[u].mn[]=t[u].mx[]=p[l].x[];

         t[u].mn[]=t[u].mx[]=p[l].x[];

         return u;

     }

     bool flag=;

     rep(i,l+,r) if(p[i].x[wd]!=p[i-].x[wd])flag=;

     if (flag) wd^=;

     D=wd; nth_element(p+l,p+mid,p++r);

     t[u].lc=bud(l,mid,wd^); t[u].rc=bud(mid+,r,wd^);

     upd(u); return u;

 }

 void dfs(int u){

     if (!t[u].siz)return;

     if (t[u].mn[]>xr||t[u].mx[]<xl||t[u].mn[]>yr||t[u].mx[]<yl)return;

     if (id[u]){ nd[++len]=id[u]; t[u].siz=; return; }

     dfs(t[u].lc); dfs(t[u].rc);

     t[u].siz=t[t[u].lc].siz+t[t[u].rc].siz;

 }

 int main(){

     freopen("jump.in","r",stdin);

     freopen("jump.out","w",stdout);

     memset(dis,,sizeof(dis));

     scanf("%d%d%d%d",&n,&m,&w,&h);

     rep(i,,n) scanf("%d%d",&p[i].x[],&p[i].x[]),p[i].id=i;

     rt=bud(,n,);

     rep(i,,m){

         scanf("%d%d%d%d%d%d",&nu,&nt,&xl,&xr,&yl,&yr);

         f[nu].push_back((data){nt,xl,xr,yl,yr});

     }

     dis[]=; vis[]=;

     for(int i=; i<(int)f[].size(); i++) Q.push(f[][i]);

     while (!Q.empty()){

         nt=Q.top().nt,xl=Q.top().xl,xr=Q.top().xr,yl=Q.top().yl,yr=Q.top().yr;

         Q.pop(); len=; dfs(rt);

         rep(i,,len){

             int u=nd[i];

             if (vis[u])continue; vis[u]=;

             dis[u]=nt;

             for (int j=; j<(int)f[u].size(); ++j){

                 data tp=f[u][j]; tp.nt+=nt; Q.push(tp);

             }

         }

     }

     rep(i,,n) printf("%d\n",dis[i]);

     return ;

 }

KD-Tree

巴特西

[NOI2019]弹跳(KD-Tree/四分树/线段树套平衡树优化建图+Dijkstra)

最新文章

热门文章

巴特西

[NOI2019]弹跳(KD-Tree/四分树/线段树套平衡树 优化建图+Dijkstra)

最新文章

热门文章

[NOI2019]弹跳(KD-Tree/四分树/线段树套平衡树优化建图+Dijkstra)