求助!线段树
查看原帖
求助!线段树
418419
ko_no_lzx_da楼主2022/3/21 12:19
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int maxx=-1;
struct nod{
	int x,y;
	int f=0;
	int x1,y1;
	int num=0x7fffffff;
}zb[100000];
int path[1000000];
bool cmp(nod w,nod u){
	return w.x<u.x;
}
bool cmp1(nod w,nod u){
	return w.num<u.num;
} 
struct node{
	int sum;
	int l,r;
}t[10000000];
int n,m;
void build(int l,int r,int n){
	if(l==r){
		t[n].sum=0;
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,n<<1);
	build(mid+1,r,n<<1|1);
	t[n].sum=t[n<<1].sum+t[n<<1|1].sum;
} 
void add(int l,int r,int n,int v){
	if(l==r){
		t[n].sum=1;
		return;
	}
	int mid=(l+r)>>1;
	if(v<=mid)add(l,mid,n<<1,v);
	if(v>mid)add(mid+1,r,n<<1|1,v);
	t[n].sum=t[n<<1].sum+t[n<<1|1].sum;
}
int find(int l,int r,int n,int L,int R){
	int ans=0;
	if(L<=l&&r<=R){
		return t[n].sum;
	}
	int mid=(l+r)>>1;
	if(L<=mid)ans+=find(l,mid,n<<1,L,R);
	if(R>mid)ans+=find(mid+1,r,n<<1|1,L,R);
	return ans;
}
int main(){
	cin >>n>>m;
	for(int i=1;i<=n;i++){
		int x=read(),y=read();
		x++;
		y++;
		zb[i].x=x,zb[i].y=y;
		maxx=max(y,maxx);
	}
	for(int i=n+1;i<=n+1+m*2;i+=2){
		int x=read(),y=read(),x1=read(),y1=read();
		x++;
		y++;
		x1++;
		y1++;
		zb[i].x=x1;
		zb[i].y=y1;
		zb[i].f=2;
		zb[i].x1=x;
		zb[i].y1=y;
		zb[i].num=i-n;
		zb[i+1].x=x;
		zb[i+1].y=y;
		zb[i+1].f=1;
		zb[i+1].x1=x1;
		zb[i+1].y1=y1;
		zb[i+1].num=i-n;
	}
	sort(zb+1,zb+1+n+m,cmp);
	build(1,maxx,1);
	for(int i=1;i<=n;i++){
		if(zb[i].f==0){
			add(1,maxx,1,zb[i].y);
		}else if(zb[i].f==1){
			path[zb[i].num]=find(1,maxx,1,1,zb[i].y)-find(1,maxx,1,1,zb[i].y1);
		}else{
			path[zb[i].num]=find(1,maxx,1,1,zb[i].y)-find(1,maxx,1,1,zb[i].y1);
		}
	}
	for(int i=1;i<=m;i++){
		cout <<path[i]<<endl;
	}
	return 0;
}


2022/3/21 12:19
加载中...