C++14(g++5.4) 解法, 执行用时: 273ms, 内存消耗: 13848K, 提交时间: 2020-04-19 19:10:20

#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i <  _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int N = 1e5 + 5;

const int inf = 2e9;

struct P {
	int x, y, z;
	P(){}
	P(int _x, int _y, int _z) {
		x = _x, y = _y, z = _z;
	}
};

int ans[N];

int cmpy(P a, P b) {
	return a.y < b.y;
}

int cmp(P a, P b) {
	if(a.x == b.x) return a.z < b.z;
	return a.x < b.x;
}

#define low(x) ((x) & -(x))
int t[N * 2];
void pla(int x, int y) {
	for(; x <= 2e5; x += low(x))
		t[x] += y;
}
int sum(int x) {
	int s = 0;
	for(; x; x -= low(x))
		s += t[x];
	return s;
}

struct Q {
	P d[N * 2]; int d0;
	void add(P a) { d[++ d0] = a;}
	void gg() {
		sort(d + 1, d + d0 + 1, cmpy);
		int id = 0, la = -inf;
		fo(i, 1, d0) {
			id += (i == 1 || d[i].y != la);
			la = d[i].y; d[i].y = id;
		}
		sort(d + 1, d + d0 + 1, cmp);
		memset(t, 0, sizeof t);
		fo(i, 1, d0) {
			if(d[i].z == -inf + 1 || d[i].z == -inf - 1) {
				pla(d[i].y, d[i].z + inf);
			} else {
				ans[d[i].z]	+= sum(d[i].y);
			}
		}
	}
} f, g, h;

int n, Q;
P a[N], b[N];

int main() {
	scanf("%d %d", &n, &Q);
	fo(i, 1, n) {
		scanf("%d %d", &a[i].x, &a[i].y);
		f.add(P(inf - a[i].x, inf - a[i].y, -inf + 1));
		g.add(P(inf - (a[i].x + a[i].y), inf - a[i].x, -inf + 1));
		h.add(P(inf - (a[i].x + a[i].y), a[i].y, -inf - 1));
	}
	fo(i, 1, Q) {
		scanf("%d %d %d", &a[i].x, &a[i].y, &a[i].z);
		if(a[i].x + a[i].y >= a[i].z) {
			f.add(P(inf - a[i].x, inf - a[i].y, i));
		} else {
			g.add(P(inf - a[i].z, inf - a[i].x, i));
			h.add(P(inf - a[i].z, a[i].y - 1, i));
		}
	}
	f.gg(); g.gg(); h.gg();
	fo(i, 1, Q) pp("%d\n", ans[i]);
}

C++11(clang++ 3.9) 解法, 执行用时: 735ms, 内存消耗: 10984K, 提交时间: 2020-04-19 14:50:55

#include <iostream>
#include <algorithm>
#include <cmath>
#define pus push_back
#define pai pair<int,int>
#define fir first
#define sec second
#define M 1000005
#define Q 1000005
using namespace std;
int n,f,jsq=0;
pai p[M];
int v[M];
int a[Q];
bool cmp(pai x,pai y)
{
	return x.fir+x.sec<y.fir+y.sec;
}
struct nod{
	int a,b,c;
	int d;
}q[Q];
bool compare(nod x,nod y)
{
	return x.c<y.c;
}
int lob(int x) 
{
    return lower_bound(v+1,v+jsq+1,x)-v;
}
struct h{
    int t[M*2];
    int s;
    int lowbit(int x) 
	{
		return x&(-x);
    }
    void ins(int x,int y) 
	{
		while(x<=s) 
		{
	    	t[x]+=y;
	    	x+=lowbit(x);
		}
    }
    int query(int x) 
	{
		int ans=0;
		while(x>0) 
		{
	    	ans+=t[x];
	    	x-=lowbit(x);
		}
		return ans;
    }
}t[2];
int main()
{
	cin>>n>>f;
	for(int i=1;i<=n;i++)
	{
		cin>>p[i].fir>>p[i].sec;
		v[++jsq]=p[i].fir;
		v[++jsq]=p[i].sec;
	}
	sort(v+1,v+jsq+1);
	jsq=unique(v+1,v+jsq+1)-v-1;
	t[0].s=t[1].s=jsq;
	sort(p+1,p+n+1,cmp);
    for(int i=1;i<=f;i++) 
	{
		cin>>q[i].a>>q[i].b>>q[i].c;
		q[i].c=max(q[i].c,q[i].a+q[i].b);
		q[i].d=i;
		a[i]=n;
    }
    sort(q+1,q+f+1,compare);
	for(int i=1;i<=n;i++) 
	{
		t[0].ins(lob(p[i].fir),1);
		t[1].ins(lob(p[i].sec),1);
    }
    int ans=0;
    for(int i=1;i<=f;i++)
	{
		while(ans<n&&p[ans+1].fir+p[ans+1].sec<q[i].c) 
		{
	    	ans++;
	    	t[0].ins(lob(p[ans].fir),-1);
	    	t[1].ins(lob(p[ans].sec),-1);
		}
		a[q[i].d]-=ans;
		a[q[i].d]-=t[0].query(lob(q[i].a)-1);
		a[q[i].d]-=t[1].query(lob(q[i].b)-1);
    }
    for(int i=1;i<=f;i++)
	cout<<a[i]<<endl; 
	return 0;
}