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;
}