```cpp
#include<algorithm>
#include<string>
int read()
{
int s=0,w=1;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0' && ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
void write(int x)
{
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
return;
}
const int N=5e6+10;
int n,m;
int c[N];
int a[N];
int ans[N][10];
int sum[N];
int lowbit(int x)
{
return x&(-x);
}
int query(int x)
{
int res=0;
while(x)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
void add(int x,int val)
{
while(x<=n)
{
c[x]+=val;
x+=lowbit(x);
}
}
struct node
{
int x,y,tag;
}t[N];
int cmp(node x,node y)
{
if(x.x!=y.x) return x.x<y.x;
if(x.y==y.y) return x.tag<y.tag;
return x.y<y.y;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();m=read();
for(int i=1;i<=n;++i)
{
t[i].x=read();t[i].y=read();t[i].tag=0;
}
for(int i=1;i<=m;++i)
{
int a=read(),b=read(),c=read(),d=read();
t[++n]={a-1,b-1,i};
t[++n]={c,d,i};
t[++n]={c,b-1,i};
t[++n]={a-1,d,i};
}
std::sort(t+1,t+n+1,cmp);
for(int i=1;i<=n;++i)
{
a[i]=t[i].y;
}
std::sort(a+1,a+n+1);
int cnt=std::unique(a+1,a+n+1)-a-1;
for(int i=1;i<=n;++i)
{
int p=std::lower_bound(a+1,a+n+1,t[i].y)-a;
if(t[i].tag) ans[t[i].tag][++sum[t[i].tag]]=query(p);
else add(p,1);
}
for(int i=1;i<=m;++i)
{
write(ans[i][4]-ans[i][3]-ans[i][2]+ans[i][1]);putchar('\n');
}
return 0;
}
by T1EM1E @ 2023-08-11 10:30:43
@[T1EM1E](/user/643058) TLE 的原因应该是离散化的时候使用了太多 `std::lower_bound`,STL 的很多函数在不开 O2 的前提下效率是很低的,现在比赛都会开 O2,不妨开 O2 提交试试。
by VectorLi @ 2023-09-02 17:13:23
@[T1EM1E](/user/643058) 如果您想在不开 O2 的前提下通过这道题,可以手写一下二分?应该提升很大
by VectorLi @ 2023-09-02 17:14:28