随机TLE求条 玄关
查看原帖
随机TLE求条 玄关
760776
zzy_zzy楼主2025/1/15 22:34
#include<bits/stdc++.h>
using namespace std;
struct node1{
    int xl,xr,yl,yr,z,id;
}a[100010];
struct node2{
    int x,y,id;
}b[100010];
bool cmp(node1 i,node1 j){
    return i.z<j.z;
}
struct TT{
    int L,R,minn;
    int xl,xr,yl,yr,fa;
    node2 pos;
}tree[400010];
int tot=0;
bool cmp1(node2 i,node2 j){
    return i.x<j.x;
}
bool cmp2(node2 i,node2 j){
    return i.y<j.y;
}
int New(){
    tot++;
    return tot;
}
int Pos[100010];
int build(int l,int r){
    if(l>r)return 0;
    if(l==r){
        int Th=New();
        tree[Th].pos=b[l];
        tree[Th].minn=b[l].id;
        tree[Th].xl=tree[Th].xr=b[l].x;
        tree[Th].yl=tree[Th].yr=b[l].y;
        Pos[b[l].id]=Th;
        return Th;
    }
    double xx=0.0,yy=0.0,xxx=0.0,yyy=0.0;
    for(int i=l;i<=r;i++){
        xx+=b[i].x,yy+=b[i].y;
    }
    xx/=(r-l+1),yy/=(r-l+1);
    for(int i=l;i<=r;i++){
        xxx+=(b[i].x-xx)*(b[i].x-xx),yyy+=(b[i].y-yy)*(b[i].y-yy);
    }
    xxx/=(r-l+1),yyy/=(r-l+1);
    int Id=l+(r-l)/2;
    if(xxx>yyy){
        nth_element(b+l,b+Id,b+r+1,cmp1);
    }
    else nth_element(b+l,b+Id,b+r+1,cmp2);
    int Th=New();
    tree[Th].pos=b[Id];
    Pos[b[Id].id]=Th;
    tree[Th].L=build(l,Id-1);
    tree[tree[Th].L].fa=Th;
    tree[Th].R=build(Id+1,r);
    tree[tree[Th].R].fa=Th;
    tree[Th].minn=min(tree[tree[Th].L].minn,min(tree[tree[Th].R].minn,b[Id].id));
    tree[Th].xl=min(tree[tree[Th].L].xl,min(tree[tree[Th].R].xl,b[Id].x));
    tree[Th].xr=max(tree[tree[Th].L].xr,max(tree[tree[Th].R].xr,b[Id].x));
    tree[Th].yl=min(tree[tree[Th].L].yl,min(tree[tree[Th].R].yl,b[Id].y));
    tree[Th].yr=max(tree[tree[Th].L].yr,max(tree[tree[Th].R].yr,b[Id].y));
    return Th;
}
bool Del[100010];
void pushup(int p){
    tree[p].minn=min(tree[tree[p].L].minn,tree[tree[p].R].minn);
    if(!Del[tree[p].pos.id])tree[p].minn=min(tree[p].minn,tree[p].pos.id);
}
int check(int a1,int b1,int c1,int d1,int a2,int b2,int c2,int d2){
    if(d1<c2||d2<c1||b1<a2||b2<a1)return 0;
    if(a1<=a2&&c1<=c2&&b2<=b1&&d2<=d1)return 1;
    return 2;
}
int ask(int p,int a,int b,int c,int d){
    int num=check(a,b,c,d,tree[p].xl,tree[p].xr,tree[p].yl,tree[p].yr);
    if(!num)return INT_MAX;
    if(num==1){
        return tree[p].minn;
    }
    int Min=INT_MAX;
    node2 Id=tree[p].pos;
    if(Id.y>=c&&Id.y<=d&&Id.x>=a&&Id.x<=b&&!Del[tree[p].pos.id])Min=tree[p].pos.id;
    if(tree[p].L)Min=min(Min,ask(tree[p].L,a,b,c,d));
    if(tree[p].R)Min=min(Min,ask(tree[p].R,a,b,c,d));
    return Min;
}
void del(int p,int x,int y,int z){
    z=Pos[z];
    tree[z].minn=min(tree[tree[z].L].minn,tree[tree[z].R].minn);
    while(z!=1){
        z=tree[z].fa;
        pushup(z);
    }
}
int ans[100010];
node2 bb[100010];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].xl>>a[i].xr>>a[i].yl>>a[i].yr>>a[i].z;
        a[i].id=i;
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>b[i].x>>b[i].y;
        b[i].id=i;
        bb[i]=b[i];
    }
    sort(a+1,a+n+1,cmp);
    tree[0].minn=INT_MAX;
    int x=build(1,m);
    for(int i=1;i<=n;i++){
        int chuan=ask(1,a[i].xl,a[i].xr,a[i].yl,a[i].yr);
        if(chuan==INT_MAX)continue;
        ans[chuan]=a[i].id;
        Del[chuan]=1;
        del(1,bb[chuan].x,bb[chuan].y,chuan);
    }
    for(int i=1;i<=m;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}
2025/1/15 22:34
加载中...