KDT 做法 80pts 求救。

#include<bits/stdc++.h>

using namespace std;

const int N = 4e5 + 5;

char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;

__inline__ int read() {
    int x=0;
    char ch=(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
    while(!(ch>='0'&&ch<='9'))
        ch=(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
    while(ch>='0'&&ch<='9') 
        x=x*10+(ch^48),ch=(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++);
    return x;
}

__inline__ void write(int x){
    if(x>9)
        write(x/10);
    ((O==obuf+(1<<21))&&(fwrite(obuf,1,O-obuf,stdout),O=obuf)),*O++=(x%10)^48;
}

struct Flush{
    ~Flush(){fwrite(obuf,1,O-obuf,stdout);}
}_;

int n, m, ans[N], now, rot, idx, book[N];

struct Point {
	int x[4], id;
} a[N], b[N], c[N << 1];

struct Node {
	Point p;
	int ls, rs, L[4], R[4], w, fa;
} tr[N];

__inline__ bool cmp(Point x1, Point x2) {
	if(x1.x[0] == x2.x[0]) {
		return x1.id < x2.id;
	}
	
	return x1.x[0] < x2.x[0];
}

__inline__ bool cmp1(Point x1, Point x2) {
	return x1.x[now] < x2.x[now];
}

#define mid (l + r >> 1)
#define ls(p) (tr[p].ls)
#define rs(p) (tr[p].rs)

__inline__ void up(int p) {
	for(int i = 0; i <= 3; i ++) {
		tr[p].L[i] = tr[p].p.x[i];
		tr[p].R[i] = tr[p].p.x[i];
		
		if(ls(p)) {
			tr[p].L[i] = min(tr[p].L[i], tr[ls(p)].L[i]);
			tr[p].R[i] = max(tr[p].R[i], tr[ls(p)].R[i]);
		}
		
		if(rs(p)) {
			tr[p].L[i] = min(tr[p].L[i], tr[rs(p)].L[i]);
			tr[p].R[i] = max(tr[p].R[i], tr[rs(p)].R[i]);
		}
	}
}

int bu(int l, int r, int op) {
	if(l > r) {
		return 0;
	}
	
	int p = ++ idx;
	now = op + 1;
	nth_element(a + l, a + mid, a + r + 1, cmp1);
	tr[p].p = a[mid];
	ls(p) = bu(l, mid - 1, (op + 1) % 3);
	rs(p) = bu(mid + 1, r, (op + 1) % 3);
	up(p);
	return p;
}

__inline__ bool out(int p, Point x) {
	if(x.x[1] > tr[p].R[1] || x.x[2] < tr[p].L[2] || x.x[3] > tr[p].R[3] || x.x[0] < tr[p].L[0]) {
		return 1;
	}
	
	return 0;
}

__inline__ bool in(int p, Point x) {
	if(x.x[1] <= tr[p].L[1] && x.x[2] >= tr[p].R[2] && x.x[3] <= tr[p].L[3]) {
		return 1;
	}
	
	return 0;
}

int qu(int p, Point x) {
	if(!p) {
		return 0;
	}
	
	if(in(p, x)) {
		return tr[p].w;
	}
	
	if(out(p, x)) {
		return 0;
	}
	
	int res = 0;
	
	if(x.x[1] <= tr[p].p.x[1] && x.x[2] >= tr[p].p.x[2] && x.x[3] <= tr[p].p.x[3]) {
		res += tr[p].w - tr[ls(p)].w - tr[rs(p)].w;
	}
	
	res += qu(ls(p), x);
	res += qu(rs(p), x);
	return res;
}

int main() {
	n = read(), m = read();
	
	for(int i = 1; i <= n; i ++) {
		a[i].x[0] = read(), a[i].x[2] = read(), a[i].x[1] = read(), a[i].x[3] = read();
		a[i].id = i;
		c[i] = a[i];
	}
	
	rot = bu(1, n, 0);
	
	for(int i = 1; i <= m; i ++) {
		b[i].x[0] = read(), b[i].x[2] = read(), b[i].x[1] = read(), b[i].x[3] = read();
		b[i].id = n + i;
		c[n + i] = b[i];
	}
	
	sort(c + 1, c + n + m + 1, cmp);
	
	for(int i = 1; i <= idx; i ++) {
		book[tr[i].p.id] = i;
		tr[ls(i)].fa = i;
		tr[rs(i)].fa = i;
	}
	
	for(int i = 1; i <= n + m; i ++) {
		if(c[i].id <= n) {
			int x = book[c[i].id];
			
			while(x) {
				tr[x].w ++;
				x = tr[x].fa;
			}
		}
		else {
			ans[c[i].id - n] = qu(rot, c[i]);
		}
	}
	
	for(int i = 1; i <= m; i ++) {
		write(ans[i]);
	    ((O==obuf+(1<<21))&&(fwrite(obuf,1,O-obuf,stdout),O=obuf)),*O++='\n';
	}
	
	return 0;
}