扫描线WA on #2
查看原帖
扫描线WA on #2
999274
CNS_5t0_0r2楼主2025/1/18 16:37
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 9,M = 5e5 + 9,V = 5e5 + 9;
int n,m;
vector<int> p[N];
int max_x,max_y;

int BIT[V];
int lowbit(int x){
	return x & (-x);
}
void update(int pos,int v){
	for(int i = pos;i <= max_y;i += lowbit(i))
		BIT[i] += v;
}
int query(int pos){
	int ret = 0;
	for(int i = pos;i;i -= lowbit(i))
		ret += BIT[i];
	return ret;
}

struct QUERY{
	int x,y,typ,id;
} q[N << 2];
bool cmp(QUERY q1,QUERY q2){
	return (q1.x ^ q2.x) ? q1.x < q2.x : q1.y < q2.y;
}
int top;
int ans[M];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		int x,y;
		cin >> x >> y;
		x++;y++;
		max_x = max(max_x,x);
		max_y = max(max_y,y);
		p[x].push_back(y);
	}
	for(int i = 1;i <= max_x;i++)
		sort(p[i].begin(),p[i].end());
	for(int i = 1;i <= m;i++){
		int x1,y1,x2,y2;
		cin >> x1 >> y1 >> x2 >> y2;
		x1++;y1++;x2++;y2++;
		q[++top] = (QUERY){x1 - 1,y1 - 1,1,i};
		q[++top] = (QUERY){x1 - 1,y2,-1,i};
		q[++top] = (QUERY){x2,y1 - 1,-1,i};
		q[++top] = (QUERY){x2,y2,1,i};
	}
	sort(q + 1,q + top + 1,cmp);
	for(int i = 1;i <= top;i++){
		for(int j = q[i - 1].x + 1;j <= q[i].x;j++)
			for(int k = 0;k < p[j].size();k++)
				update(p[j][k],1);
		ans[q[i].id] += q[i].typ * query(q[i].y);
	}
	for(int i = 1;i <= m;i++)
		cout << ans[i] << '\n';
	return 0;
}
2025/1/18 16:37
加载中...