1 条题解
-
0
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
- 上传者