二维数点/二维偏序

模型：

给定二维点集，给定矩阵集，问每个矩阵中有多少个点。

此处二维偏序关系的问题也大都如此。

这里使用树状数组和二维前缀和容斥拆解思想求解。

例题：

P2163 [SHOI2007] 园丁的烦恼

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int N = 5e5 + 10;
int n, m;
int tr[N];
struct node
{
    int x, y, val, id;
    bool operator<(node t)
    {
        if (x != t.x)
        {
            return x < t.x;
        }
        else
        {
            return y < t.y;
        }
    }
};

int lowbit(int x)
{
    return x & -x;
}

void update(int idx, int val)
{
    for (int i = idx; i <= N - 1; i += lowbit(i))
    {
        tr[i] += val;
    }
}

int query(int idx)
{
    ll res = 0;
    for (int i = idx; i; i -= lowbit(i))
    {
        res += tr[i];
    }
    return res;
}

void solve()
{

    scanf("%d %d", &n, &m);
    vector<pii> v(n + 1);
    vector<int> p;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d", &v[i].fi, &v[i].se);
        v[i].fi++;
        v[i].se++;
        p.push_back(v[i].fi);
        p.push_back(v[i].se);
    }
    vector<node> q(1);
    for (int i = 1; i <= m; i++)
    {
        int x1, x2, y1, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        x1++;
        x2++;
        y1++;
        y2++;
        q.push_back({x1 - 1, y1 - 1, 1, i});
        q.push_back({x1 - 1, y2, -1, i});
        q.push_back({x2, y1 - 1, -1, i});
        q.push_back({x2, y2, 1, i});
        p.push_back(x1 - 1);
        p.push_back(y1 - 1);
        p.push_back(x1 - 1);
        p.push_back(y1 - 1);
        p.push_back(x2);
        p.push_back(y2);
    }
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    auto find = [&](int x)
    {
        int t = lower_bound(p.begin(), p.end(), x) - p.begin() + 1;
        return t;
    };
    sort(v.begin() + 1, v.end());
    sort(q.begin() + 1, q.end());
    int cur = 1;
    vector<int> ans(m + 1);
    for (int i = 1; i <= q.size() - 1; i++)
    {
        while (cur <= n && v[cur].fi <= q[i].x)
        {
            int t = find(v[cur].se);
            // cout << t << ' ' << v[cur].se << endl;
            update(t, 1);
            cur++;
        }
        // cout << q[i].id << ' ' << q[i].x << ' ' << q[i].y << ' ' << find(q[i].y) << ' ' << query(find(q[i].y)) * q[i].val << endl;
        ans[q[i].id] += query(find(q[i].y)) * q[i].val;
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%lld\n", ans[i]);
    }
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}

P3755 [CQOI2017] 老C的任务

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi first
#define se second
const int N = 1e6 + 10;
int n, m;
ll tr[N];
struct node
{
    ll x, y, val, id;
    bool operator<(node t)
    {
        if (x != t.x)
        {
            return x < t.x;
        }
        else
        {
            return y < t.y;
        }
    }
};

struct base
{
    ll x, y, p;
    bool operator<(base t)
    {
        if (x != t.x)
        {
            return x < t.x;
        }
        else
        {
            return y < t.y;
        }
    }
};

ll lowbit(int x)
{
    return x & -x;
}

void update(int idx, int val)
{
    for (int i = idx; i <= N - 1; i += lowbit(i))
    {
        tr[i] += val;
    }
}

ll query(int idx)
{
    ll res = 0;
    for (int i = idx; i; i -= lowbit(i))
    {
        res += tr[i];
    }
    return res;
}

void solve()
{
    cin >> n >> m;
    vector<ll> d;
    vector<base> v(1);
    for (int i = 1; i <= n; i++)
    {
        ll x, y, p;
        scanf("%lld %lld %lld", &x, &y, &p);
        v.push_back({x, y, p});
        // d.push_back(x);
        d.push_back(y);
    }
    vector<node> q(1);
    for (int i = 1; i <= m; i++)
    {
        ll x1, y1, x2, y2;
        scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
        q.push_back({x1 - 1, y1 - 1, 1, i});
        q.push_back({x1 - 1, y2, -1, i});
        q.push_back({x2, y1 - 1, -1, i});
        q.push_back({x2, y2, 1, i});
        // d.push_back(x1);
        // d.push_back(y1);
        // d.push_back(x1 - 1);
        d.push_back(y1 - 1);
        // d.push_back(x2);
        d.push_back(y2);
    }
    sort(d.begin(), d.end());
    d.erase(unique(d.begin(), d.end()), d.end());
    auto find = [&](ll x) -> ll
    {
        auto t = lower_bound(d.begin(), d.end(), x) - d.begin() + 1;
        return t;
    };
    vector<ll> ans(m + 1);
    sort(v.begin() + 1, v.end());
    sort(q.begin() + 1, q.end());
    int cur = 1;
    for (int i = 1; i < q.size(); i++)
    {
        while (cur <= n && q[i].x >= v[cur].x)
        {
            auto t = find(v[cur].y);
            update(t, v[cur].p);
            cur++;
        }
        ans[q[i].id] += query(find(q[i].y)) * q[i].val;
    }
    for (int i = 1; i <= m; i++)
    {
        printf("%lld\n", ans[i]);
    }
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}