P1437 三角查询 题解

首先这道题要我们求一个等腰直角三角形内的点的个数。

这个等腰直角三角形有一个很好的性质，三个点都在格点上，两条边都在格边上。

那么我们就可以想到一个三维数点的做法。

即有三条限制：

1. $x >= x_i$

2. $y >= y_i$

3. $x + y <= x_i + y_i$

所以 K-D Tree 来写。

但是我们观察一下就可以发现 $x + y$ 这一维不是独立的，

即 $x + y$ 可以用 $x$ 和 $y$ 来表示。所以我们可以证明，用二维数点就可以写。

接下来我们考虑怎么用二维数点写。

我们把图像画出来：

观察到可以把这个图切成三部分：

那么我们观察一下，以 $x + y$ 为一维，那么 $\text{\textcircled 1}\ +\ \text{\textcircled 2}\ +\ \text{\textcircled 3}$ 就非常好算。

然后我们考虑如何计算 $\text{\textcircled 1}$ 和 $\text{\textcircled 2}$ 怎么算。

注意到 $\text{\textcircled 1}$ 只与 $x + y$ 和 $x$ 有关，$\text{\textcircled 2}$ 只与 $x + y$ 和 $y$ 有关。

那么我们二维数点只需要扫描 $x + y$ 这一维，用一些数据结构维护另一维。然后就把这道题写出来了。

代码如下:

#include<bits/stdc++.h>
#define lowbit(x) (x & - x)
using namespace std;
const int N = 1e6 + 15;
const int M = 3e6 + 15;
const int C = 1e6;
int n,q;
struct Point{
    int x,y;
}pt[N];
namespace BIT{
    int tr[3][M];
    void add(int id,int x,int y){
        for(;x < M;x += lowbit(x))
            tr[id][x] += y;
        return ;
    }
    int ask(int id,int x,int y){
        int res = 0;x --;
        for(;x or y;x -= lowbit(x),y -= lowbit(y))
            res += tr[id][y] - tr[id][x];
        return res;
    }
}
int ans[N];
vector<array<int,4>> Q[M];
vector<int> pit[M];
void solve(){
    cin >> n >> q;
    for(int i = 1;i <= n;i ++){
        cin >> pt[i].x >> pt[i].y;
        pit[pt[i].x + pt[i].y].push_back(pt[i].x);
        BIT::add(0,pt[i].x + pt[i].y,1);
    }
    for(int i = 1;i <= q;i ++){
        int x,y,d;cin >> x >> y >> d;
        ans[i] += BIT::ask(0,x + y,x + y + d);
        Q[x + y - 1].push_back({1,1,x,i});
        Q[x + y + d].push_back({-1,1,x,i});
        Q[x + y - 1].push_back({1,2,y,i});
        Q[x + y + d].push_back({-1,2,y,i});
    }
    for(int i = 1;i < M;i ++){
        for(auto x : pit[i]){
            int y = i - x;
            BIT::add(1,x,1);
            BIT::add(2,y,1);
        }
        for(auto _ : Q[i]){
            int fg = _[0],tp = _[1],t = _[2],id = _[3];
            ans[id] += fg * BIT::ask(tp,1,t - 1);
        }
    }
    for(int i = 1;i <= q;i ++)
        cout << ans[i] << '\n';
}
signed main(){
    freopen("triangular.in","r",stdin);
    freopen("triangular.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

但是交上去后发现 MLE 了，为什么呢？

其实是因为桶排用非常多的 $vector$，然后空间直接爆炸。

所以我们把桶排替换为 排序 + 指针就可以通过此题。

通过代码(128 Mib)：

#include<bits/stdc++.h>
#define lowbit(x) (x & - x)
using namespace std;
const int N = 1e6 + 15;
const int M = 3e6 + 15;
const int C = 1e6;
int n,q;
namespace BIT{
    int tr[M];
    void add(int x,int y){
        for(;x < M;x += lowbit(x))
            tr[x] += y;
        return ;
    }
    int ask(int x,int y){
        int res = 0;x --;
        for(;x or y;x -= lowbit(x),y -= lowbit(y))
            res += tr[y] - tr[x];
        return res;
    }
    void clear(){
        for(int i = 1;i < M;i ++)
            tr[i] = 0;
        return ;
    }
}
int ans[N];
vector<array<int,5>> Q;
vector<pair<int,int>> pit;
void solve(){
    cin >> n >> q;
    for(int i = 1;i <= n;i ++){
        int x,y;cin >> x >> y;
        pit.push_back({x,y});
        BIT::add(x + y,1);
    }
    for(int i = 1;i <= q;i ++){
        int x,y,d;cin >> x >> y >> d;
        ans[i] += BIT::ask(x + y,x + y + d);
        Q.push_back({x + y - 1,x,y,1,i});
        Q.push_back({x + y + d,x,y,-1,i});
    }
    BIT::clear();
    sort(Q.begin(),Q.end(),[&](const array<int,5> &f,const array<int,5> &g){
        return f[0] < g[0];
    });
    sort(pit.begin(),pit.end(),[&](const pair<int,int> &f,const pair<int,int> &g){
        return f.first + f.second < g.first + g.second;
    });
    int fr = 0,nt = 0;
    for(int i = 1;i < M;i ++){
        while(nt < pit.size() && pit[nt].first + pit[nt].second == i){
            int x = pit[nt].first,y = pit[nt].second;
            BIT::add(x,1);nt ++;
        }
        while(fr < Q.size() && Q[fr][0] == i){
            auto _ = Q[fr];
            int fg = _[3],t = _[1],id = _[4];
            ans[id] += fg * BIT::ask(1,t - 1);
            fr ++;
        }
    }
    fr = 0;nt = 0;
    BIT::clear();
    for(int i = 1;i < M;i ++){
        while(nt < pit.size() && pit[nt].first + pit[nt].second == i){
            int x = pit[nt].first,y = pit[nt].second;
            BIT::add(y,1);nt ++;
        }
        while(fr < Q.size() && Q[fr][0] == i){
            auto _ = Q[fr];
            int fg = _[3],t = _[2],id = _[4];
            ans[id] += fg * BIT::ask(1,t - 1);
            fr ++;
        }
    }
    for(int i = 1;i <= q;i ++)
        cout << ans[i] << '\n';
}
signed main(){
    freopen("triangular.in","r",stdin);
    freopen("triangular.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T = 1;
    while(T --) solve();
    return 0;
}

直接求范围内的点不好求，所以考虑换种思路：求不在范围内的点，用三角形三边所在直线将平面分割
设查询为 $X,Y,D$
红色区域内点集可表示为 $\{(x,y)|x<X\}$
黄色区域内点集可表示为 $\{(x,y)|y<Y\}$
蓝色区域内点集可表示为 $\{(x,y)|x+y>X+Y+D\}$（此处涉及高中数学直线一般式，但是可以通过看图理解）
因此，根据容斥定理，可以得出

其中单色区域较为好求，排序后双指针或二分均可 对于不同色块的交集，二维数点即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef array<int,4> ARR;
typedef pair<int,int> PII;
const int N = 1e6 + 5;
int n,q,ans[N];
ARR a[N],p[N];
bool cmpx(ARR a,ARR b) { return a[0] < b[0];}
bool cmpy(ARR a,ARR b) { return a[1] < b[1];}
bool cmpl(ARR a,ARR b) { return a[2] > b[2];}
struct BIT {
	int tr[N];
	void add(int x) {
		for(;x < N;x += x & -x) tr[x] ++;
	}
	int ask(int x) {
		int ans = 0;
		for(;x;x -= x & -x) ans += tr[x];
		return ans;
	}
} tr[3];
void solve() {
	cin >> n >> q;
	for(int i = 1;i <= n;i ++) {
		cin >> a[i][0] >> a[i][1];
		a[i][2] = a[i][0] + a[i][1];
	}
	for(int i = 1;i <= q;i ++) {
		cin >> p[i][0] >> p[i][1] >> p[i][2];
		p[i][2] += p[i][0] + p[i][1];
		ans[p[i][3] = i] = n;
	}
	sort(a + 1,a + n + 1,cmpx);
	sort(p + 1,p + q + 1,cmpx);
	for(int i = 1,j = 0;i <= q;i ++) {
		while(j < n && a[j + 1][0] < p[i][0]) {
			tr[0].add(a[++ j][1]);
		}
		ans[p[i][3]] -= j;// x < X
		ans[p[i][3]] += tr[0].ask(p[i][1] - 1);// x < X && y < Y
	}
	sort(a + 1,a + n + 1,cmpy);
	sort(p + 1,p + q + 1,cmpy);
	for(int i = 1,j = 0;i <= q;i ++) {
		while(j < n && a[j + 1][1] < p[i][1]) j ++;
		ans[p[i][3]] -= j;// y < Y
	}
	sort(a + 1,a + n + 1,cmpl);
	sort(p + 1,p + q + 1,cmpl);
	for(int i = 1,j = 0;i <= q;i ++) {
		while(j < n && a[j + 1][2] > p[i][2]) {
			j ++;
			tr[1].add(a[j][0]);
			tr[2].add(a[j][1]);
		}
		ans[p[i][3]] -= j;// x + y > X + Y + D
		ans[p[i][3]] += tr[1].ask(p[i][0] - 1);// x < X && x + y > X + Y + D
		ans[p[i][3]] += tr[2].ask(p[i][1] - 1);// y < Y && x + y > X + Y + D
	}
	for(int i = 1;i <= q;i ++) {
		cout << ans[i] << "\n";
	}
}
signed main() {
	freopen("triangular.in","r",stdin);
	freopen("triangular.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t --) solve();
	return 0;
}

如果直接查询，这是一个三维数点的形式，所以只能用 CDQ 分治等方法做到 $O(n \log^2 n)$ 的时间复杂度。

观察这个问题的性质，三角形的区域 $(x',y')$,$(x' + d,y')$,$x',y' + d$，相当于总的区域，减去 $x < x'$,$y < y'$,$x + y > x' +y' + d$ 这三个半平面，然后补上三个被减了两次的区域，也就是 $x < x'$ 且 $< y'$，$x < x'$ 且 $x + y > x' + y' + d$ 和 $y < y'$ 且 $x + y > x' + y' + d$ 这三部分。

这三部分都是一个二维数点的形式，所以可以做到 $O(n\log n)$ 的时间复杂度。