园丁的烦恼
题目链接：https://www.luogu.org/problem/P2163
数据范围：略。
题解：
树套树过不去，那就$CDQ$分治好了。
有点小细节，但都是$CDQ$分治必要的。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 1000010
using namespace std;
struct Node
{
int x,y,f,id;
}q[N<<2];
int tree[10000010];
int mx=0;
int ans[N];
inline bool cmp(const Node &a,const Node &b)
{
return a.x!=b.x?a.x<b.x:(a.y!=b.y?a.y<b.y:a.id<b.id);
}
int a,b,c,d;
int cnt;
inline int lowbit(int x){return x&(-x);}
void fix(int x)
{
// if(!x) x++;
// puts("fix");
for(int i=x;i<=mx+1;i+=lowbit(i))
{
// printf("aha %d
",i);
tree[i]++;
}
}
int query(int x)
{
// puts("query");
int ans=0;
for(int i=x;i>=1;i-=lowbit(i))
{
ans+=tree[i];
}
return ans;
}
int main()
{
int n,m; cin >> n >> m ;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&q[i].x,&q[i].y);
q[i].x++,q[i].y++;
mx=max(mx,q[i].y);
}
cnt=n;
// puts("Fuck 1");
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
c++,d++;
q[++cnt].x=c; q[cnt].y=d; q[cnt].f=1; q[cnt].id=i;
q[++cnt].x=c; q[cnt].y=b; q[cnt].f=-1; q[cnt].id=i;
q[++cnt].x=a; q[cnt].y=d; q[cnt].f=-1; q[cnt].id=i;
q[++cnt].x=a; q[cnt].y=b; q[cnt].f=1; q[cnt].id=i;
}
// printf("Gun %d
",cnt);
// puts("Fuck 2");
sort(q+1,q+cnt+1,cmp);
for(int i=1;i<=cnt;i++)
{
// printf("Shit %d
",i);
if(!q[i].id) fix(q[i].y);
else ans[q[i].id]+=query(q[i].y)*q[i].f;
}
// puts("Fuck 3");
for(int i=1;i<=m;i++)
{
printf("%d
",ans[i]);
}
return 0;
}