求助求助!!!
查看原帖
求助求助!!!
418419
ko_no_lzx_da楼主2022/3/22 13:56
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
inline int read(){
	int flag=1;
	int x=0;
	char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>'0'&&ch<'9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*flag;
} 
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){
	if(w.x==u.x)return w.f>u.f;
	return w.x<u.x;
}

struct node{
	int sum;
	int l,r;
}t[10000000];
int n,m;
void build(int l,int r,int n){
	t[n].l=l,t[n].r=r; 
	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++;
		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){
	if(L>R)return 0;
	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();
		//int x,y;
		//cin >>x>>y;
		x++;
		y++;
		zb[i].x=x,zb[i].y=y;
		zb[i].f=2;
		maxx=max(y,maxx);
	}
	for(int i=1;i<=m*2;i+=2){
		int x=read(),y=read(),x1=read(),y1=read();
	//	int x,y,x1,y1;
	//	cin >>x>>y>>x1>>y1;
		x++;
		y++;
		x1++;
		y1++;
		zb[i+n].x=x1;
		zb[i+n].y=y1;
		zb[i+n].f=1; 
		zb[i+n].x1=x;
		zb[i+n].y1=y;
		zb[i+n].num=n-i-1;
		zb[i+1+n].x=x;
		zb[i+1+n].y=y;
		zb[i+1+n].f=3;
		zb[i+1+n].x1=x1;
		zb[i+1+n].y1=y1;
		zb[i+1+n].num=n-i-1;
	}
	sort(zb+1,zb+1+n+m*2,cmp);
//	bool cmp (nod x, nod y) {
//		if (x.1<y.1) return 1;
//		if (x.1>y.1) return 0;
//		return x.r < y.r;
//	}
//	for(int i=1;i<=n+m*2;i++){
//		cout <<zb[i].x<<" "<<zb[i].y<<" "<<zb[i].f<<endl;
//	}
	build(1,maxx,1);
	for(int i=1;i<=n+m*2;i++){
		if(zb[i].f==2){
			add(1,maxx,1,zb[i].y);
//			int t2=1,t1=1;
//			for(int j=1;j<=9;j++){
//				cout <<j<<":["<<t[j].l<<" "<<t[j].r<<"]"<<"("<<t[j].sum<<") ";
//				if(t2==j){
//					cout <<endl;
//					t2+=2*t1;
//					t1++;
//				}
//			}
//			cout <<i<<endl; 
		}else if(zb[i].f==3){
			//cout <<"1:"<<find(1,maxx,1,1,zb[i].y)<<" "<<find(1,maxx,1,1,zb[i].y1)<<" "<<zb[i].num<<endl;
			path[zb[i].num]=find(1,maxx,1,1,zb[i].y)-find(1,maxx,1,1,zb[i].y1);
		}else{
			//cout <<"2:"<<find(1,maxx,1,1,zb[i].y)<<" "<<find(1,maxx,1,1,zb[i].y1-1)<<endl;
			path[zb[i].num]=find(1,maxx,1,1,zb[i].y)-find(1,maxx,1,1,zb[i].y1-1);
		}
	}
	for(int i=1;i<=m;i++){
		cout <<path[i]<<endl;
	}
	return 0;
}


2022/3/22 13:56
加载中...