标签：园丁 struct int 烦恼 t1 cc SHOI2007 n1 500005
- 二维数点问题
- 我们通过扫描线可以将静态的二维问题转换为动态的一维问题
- 维护动态的一维问题就使用数据结构维护序列
点击查看代码
#include <bits/stdc++.h>
using namespace std;
struct t1
{
int x,y;
}t[500005];
struct q1
{
int x1,y1,x2,y2;
}q[500005];
struct l1
{
int x,y1,y2,id,opt;
}l[1000005];
int c[10000005],ans[500005];
int read1()
{
char cc=getchar();
while(!(cc>=48&&cc<=57))
{
if(cc=='-')
{
break;
}
cc=getchar();
}
bool f=false;
int s=0;
if(cc=='-')
{
f=true;
}
else
{
s=cc-48;
}
while(1)
{
cc=getchar();
if(cc>=48&&cc<=57)
{
s=s*10+cc-48;
}
else
{
break;
}
}
if(f==true)
{
s=-s;
}
return s;
}
int lowbit(int n)
{
return n&(-n);
}
void add(int n1)
{
if(n1==0)
{
c[0]++;
return;
}
while(n1<=10000000)
{
c[n1]++;
n1+=lowbit(n1);
}
}
int ask(int n1)
{
int s=0;
while(n1>0)
{
s+=c[n1];
n1-=lowbit(n1);
}
return s+c[0]*(n1>=0);
}
bool cmpt(t1 a,t1 b)
{
return a.x<b.x;
}
bool cmpl(l1 a,l1 b)
{
return a.x<b.x;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
t[i].x=read1();
t[i].y=read1();
}
for(int i=1;i<=m;i++)
{
q[i].x1=read1();
q[i].y1=read1();
q[i].x2=read1();
q[i].y2=read1();
l[i].x=q[i].x1-1;
l[i+m].x=q[i].x2;
l[i].y1=l[i+m].y1=q[i].y1;
l[i].y2=l[i+m].y2=q[i].y2;
l[i].id=l[i+m].id=i;
l[i].opt=-1;
l[i+m].opt=1;
}
sort(t+1,t+n+1,cmpt);
sort(l+1,l+2*m+1,cmpl);
int j=0;
for(int i=1;i<=2*m;i++)
{
while(j+1<=n&&t[j+1].x<=l[i].x)
{
j++;
add(t[j].y);
}
ans[l[i].id]+=(l[i].opt*(ask(l[i].y2)-ask(l[i].y1-1)));
}
for(int i=1;i<=m;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
标签：园丁,
struct,
int,
烦恼,
t1,
cc,
SHOI2007,
n1,
500005
From： https://www.cnblogs.com/watersail/p/18332163