1 条题解

  • 0
    @ 2026-9-23 15:54:56

    SOLUTION

    二维数点板子题,采用主席树做法。

    CODE

    #include<bits/stdc++.h>
    using namespace std;
    // #define int long long
    #define fi first
    #define se second
    int T,n,m;
    struct point{
        int x,y;
        bool operator<(const point &k)const{
            return x<k.x;
        }
    }a[501000];
    struct query{
        int xl,yl,xr,yr;
    }q[501000];
    map<int,int> xp,yp;
    int dat[20001000],ls[20001000],rs[20001000];
    int rt[1501000],tot;
    void make_rt(int p){
        rt[p]=rt[p-1];
    }
    void push_up(int p){
        dat[p]=dat[ls[p]]+dat[rs[p]];
    }
    void update(int &p,int fa,int L,int R,int pos){
        if(p==fa) p=++tot,dat[p]=dat[fa],ls[p]=ls[fa],rs[p]=rs[fa];
        if(L==R){
            dat[p]++;
            return;
        }
        int mid=(L+R)>>1;
        if(pos<=mid) update(ls[p],ls[fa],L,mid,pos);
        else update(rs[p],rs[fa],mid+1,R,pos);
        push_up(p);
    }
    int qry(int p,int fa,int L,int R,int l,int r){
    	if(!p) return 0;
    	if(L>=l&&R<=r) return dat[p]-dat[fa];
    	int mid=(L+R)>>1,res=0;
    	if(l<=mid) res+=qry(ls[p],ls[fa],L,mid,l,r);
    	if(r>mid) res+=qry(rs[p],rs[fa],mid+1,R,l,r);
    	return res;
    }
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a[i].x>>a[i].y;
            xp[a[i].x]=1,yp[a[i].y]=1;
        }
        for(int i=1;i<=m;i++){
            cin>>q[i].xl>>q[i].yl>>q[i].xr>>q[i].yr;
            xp[q[i].xl]=1,yp[q[i].yl]=1,xp[q[i].xr]=1,yp[q[i].yr]=1;
        }
        int N=0,V=0;
        for(auto &i:xp){
            i.se=++N;
        }
        for(auto &i:yp){
            i.se=++V;
        }
        for(int i=1;i<=n;i++){
            a[i].x=xp[a[i].x],a[i].y=yp[a[i].y];
        }
        for(int i=1;i<=m;i++){
            q[i].xl=xp[q[i].xl],q[i].yl=yp[q[i].yl],q[i].xr=xp[q[i].xr],q[i].yr=yp[q[i].yr];
        }
        sort(a+1,a+1+n);
        for(int i=1;i<=n;i++){
            for(int j=a[i-1].x+1;j<=a[i].x;j++){
                make_rt(j);
            }
            update(rt[a[i].x],rt[a[i].x-1],1,V,a[i].y);
        }
        for(int i=a[n].x+1;i<=N;i++){
            make_rt(i);
        }
        for(int i=1;i<=m;i++){
            cout<<qry(rt[q[i].xr],rt[q[i].xl-1],1,V,q[i].yl,q[i].yr)<<'\n';
        }
        return 0;
    }
    

    信息

    ID
    880
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    61
    已通过
    9
    上传者