[NOI2019] d跳_C_内存溢出

文章目录

- - 题面
  - 得分情况
  - 题解
  - - 32pts: n , m ≤ 100 n,m\leq 100 n,m≤100
    - 52pts: L i = R i , D i = U i L_i=R_i,D_i=U_i Li=Ri,Di=Ui
    - 72pts: h = 1 h=1 h=1
    - 72~88pts:
    - 100pts(线段树套set):
    - 100pts(K-D Tree):

题面

得分情况

96~100pts: 95
88pts: 42
72pts: 140

题解 32pts: n , m ≤ 100 n,m\leq 100 n,m≤100

数据比较小，应该怎么乱搞都能过吧…

52pts: L i = R i , D i = U i L_i=R_i,D_i=U_i Li=Ri,Di=Ui

边数很少，直接暴力最短路。

72pts: h = 1 h=1 h=1

二维退化为一维，线段树优化建图即可。

~~暴力分怎么这么多~~

72~88pts:

一维可以线段树优化建图，那么二维线段树不就行了么。
外层线段树维护 x x x坐标，每个节点是一个维护 y y y坐标的线段树。
连边时，先找到 x x x坐标对应的点，每个点查询 y y y坐标对应的点。
但内存限制只有125MB。所以这样直接写不能拿到100pts,只能拿到72~88pts左右。

100pts(线段树套set):

考虑优化二维线段树的做法:
考虑迪杰斯特拉的算法流程，全局最小值不会被再次更新，也就是说，一个点成为全局最小值就可以直接删掉。
那么树套树的内层可以直接用空间复杂度为 O ( n ) O(n) O(n)的set维护.不用直接连边，从1号点出发指向一个最小的矩阵，将矩阵内的点更新 d i s t dist dist并由这些点向外拓展，而后直接把这些矩阵里的点删掉，以此类推。
由于每个元素只会被删除扩展一次，所以时间复杂度为 O ( n l o g 2 2 n ) O(nlog_2^2n) O(nlog22n)。
空间复杂度 O ( n l o g n + m ) O(nlogn+m) O(nlogn+m)。

参考代码:

#include
#define pa pair
#define fir first
#define sec second
#define mkp make_pair
using namespace std;
typedef long long ll;
typedef unsigned int uit;
const int N=1e5+5e4+10;
int n,m,W,H;bool vis[N];int dist[N];
struct city{
    int id,x,y;
    bool operator <(city yy)const{
        if(y!=yy.y) return y<yy.y;
        return id<yy.id;
    }
}s[N];
struct E{
    int p,t,L,R,D,U;
}e[N];
struct Go{
    int x,v;
    bool operator<(Go y)const{
        return v>y.v;
    }
}x;
set<city> v[N*2];
vector<int> g[N];
priority_queue<Go> Q;
queue<int> gar;
void upd(int p,int l,int r,int R){
    v[p].insert(s[R]);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(s[R].x<=mid) upd(p<<1,l,mid,R);
    else upd(p<<1|1,mid+1,r,R);
}
void Del(int p,int l,int r,int R){
    v[p].erase(s[R]);
    if(l==r) return;
    int mid=(l+r)>>1;
    if(s[R].x<=mid) Del(p<<1,l,mid,R);
    else Del(p<<1|1,mid+1,r,R);
}
void Erase(int p,int l,int r,int X,int V){
    int ql=e[X].L,qr=e[X].R;
    if(l>qr||r<ql) return;
    if(ql<=l&&qr>=r){
        set<city>::iterator it=lower_bound(v[p].begin(),v[p].end(),(city){0,n+1,e[X].D});
        for(;it!=v[p].end()&&(*it).y<=e[X].U;it++){
            dist[(*it).id]=V;gar.push((*it).id);
            for(auto y:g[(*it).id])  Q.push({y,e[y].t+V});
        }
        while(!gar.empty()) Del(1,1,n,gar.front()),gar.pop();
        return;
    }
    int mid=(l+r)>>1;
    Erase(p<<1,l,mid,X,V);Erase(p<<1|1,mid+1,r,X,V);
}
int main(){
//    freopen(".in","r",stdin);
//    freopen(".out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&W,&H);
    for(int i=1;i<=n;i++) scanf("%d%d",&s[i].x,&s[i].y),s[i].id=i,upd(1,1,n,i);
    for(int i=1;i<=m;i++) scanf("%d%d%d%d%d%d",&e[i].p,&e[i].t,&e[i].L,&e[i].R,&e[i].D,&e[i].U),g[e[i].p].push_back(i);
    e[0].L=e[0].R=s[1].x;e[0].U=e[0].D=s[1].y;
    Q.push({0,0});
    while(Q.size()){
        x=Q.top();Q.pop();
        if(vis[x.x]) continue;
        vis[x.x]=1;
        Erase(1,1,n,x.x,x.v);
    }
    for(int i=2;i<=n;i++) printf("%d\n",dist[i]);
    return 0;
}