题目传送门(BZOJ)
>原文链接<

题解 :

嘛~, 题意说的很明白了, 就是二维数点, 我们把询问离线, 顺便离散化.

首先按$x$排序, 这样树状数组查前缀的时候就可以不用管$x$这维了,因为需要减掉的还没加进来.

我们把每个点当成一个插入的操作, 把每个询问当成四个查询的操作, 一起排序, 注意当坐标一样的时候优先插入.

至于四个查询, 就是一个前缀和加容斥, 老套路了.

$ans[q[i].id]+=q[i].opt\times query()$,

插入时不$query()$, $opt=0$插入, $opt=1$容, $opt=-1$斥.(理解就好)

代码 :

#include <cctype>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>const int N = 10100000;int c[N], n, m, _, ans[N>>2];struct node { int x,y,id,opt; node(){} node(int x, int y, int id, int opt) : x(x), y(y), id(id), opt(opt) {} bool operator < (const node &a) const { return x == a.x? id < a.id: x<a.x; }}a[N>>2];inline char nc() { static char buf[100000], *p1, *p2; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int rd() { int x=0; char ch=nc(); while(ch<'0'||ch>'9') ch=nc(); while(ch>='0'&&ch<='9') x = (x<<1)+(x<<3)+ch - 48,ch = nc(); return x;}void change(int x,int y) {for(int i = x; i<N; i+=(i&-i)) c[i]+=y;}int query(int x) {int ret=0; for(int i = x; i; i-=(i&-i)) ret+=c[i]; return ret;}int main() { n=rd(); m=rd(); for(int i = 1; i <=n ;i ++ ) { int x, y, z, w; a[i].x=rd()+2; a[i].y=rd()+2; a[i].id=-1; } _=n; for(int i = 1; i <=m ;i ++ ) { int x, y, z, w; x=rd()+2; y=rd()+2; z=rd()+2; w=rd()+2; a[++_]=node(z, w, i, 1); a[++_]=node(z, y-1, i, -1); a[++_]=node(x-1, w, i, -1); a[++_]=node(x-1, y-1, i, 1); } std :: sort(a+1, a+_+1); for(int i = 1; i <= _ ;i ++ ) { if(a[i].id==-1) { change(a[i].y,1); }else { ans[a[i].id]+=a[i].opt*query(a[i].y); } } for(int i = 1; i <=m ;i ++ ) printf("%d\n", ans[i]);}