1：扫描线+树状数组
题意
平面上有n个点(xi,yi)。回答q个询问，每个询问给定一个矩形[X1,X2]×[Y1,Y2]，询问矩形里面有多少个点。
输入格式
第一行两个整数n,q(1≤n,q≤2×105)。
接下来n行，每行两个整数xi,yi(1≤xi,yi≤109)。
接下来q行，每行四个整数X1,X2,Y1,Y2(1≤X1≤X2≤109,1≤Y1≤Y2≤109)。
输出格式
对于每组询问，输出一个数表示答案。
样例输入
5 5
1 3
2 5
3 2
4 4
5 1
1 5 1 5
2 4 3 5
1 3 2 5
100 100 100 100
1 1 3 3
样例输出
5
2
3
0
1
点击查看代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
int n,m,k;
struct now{
int a;
int b;
int c;
int d;
};
vector<now>seg;
bool cmp(now l, now r)//排序注意点
{
if(l.a==r.a)
return l.c < r.c;
return l.a < r.a;
}
int num[N],cnt[N];
void modify(int l,int r)
{
for(;l <= k;)
{
num[l]+=r;
l += (l&-l);
}
}
int query(int l)
{
int r = 0;
for(;l;)
{
r += num[l];
l -= (l&-l);
}
return r;
}
void solve()
{
cin >> n >> m;
vector<int> ans;
for(int i = 1;i <= n;i ++)
{
int x,y;
cin >> x >> y;
seg.push_back({y,x,0,0});
ans.push_back(x);
}
for(int i = 1;i <= m;i ++)
{
int x,y,xx,yy;
cin >> x >> xx >> y >> yy;
seg.push_back({yy,xx,1,i});
seg.push_back({y-1,x-1,1,i});
seg.push_back({y-1,xx,2,i});
seg.push_back({yy,x-1,2,i});
}
sort(seg.begin(),seg.end(),cmp);
sort(ans.begin(),ans.end());
ans.erase(unique(ans.begin(),ans.end()),ans.end());
k = seg.size();
for(int i = 0;i < seg.size();i ++)
{
if(seg[i].c == 0)
{
int pos = lower_bound(ans.begin(),ans.end(),seg[i].b)-ans.begin()+1;
modify(pos,1);//统计前缀和
}
else
{
int pos = upper_bound(ans.begin(),ans.end(),seg[i].b)-ans.begin();
int res = query(pos);
if(seg[i].c==1)
cnt[seg[i].d]+=res;
else
cnt[seg[i].d]-=res;
}
}
for(int i = 1;i <= n;i ++)
cout << cnt[i] << '\n';
}
signed main()
{
int tt = 1;
//sc(tt);
while(tt--)
{
solve();
}
}