算法竞赛模板

前置知识–二维数点

P10814 【模板】离线二维数点

前缀和配合树状数组

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _ cout << "----------" << endl
#define int long long
struct node {
    int id, v, f;
};
const int N = 2e6+5;
vector<node> b[N];

struct bit {
    int n;
    vector<int> a;
    bit(int _n) : n(_n) {
        a.assign(n+1,0);
    }
    void ad(int p, int x) {
        for (int i = p; i <= n; i += i & -i) {
            a[i] += x;
        }
    }
    int qr(int p) {
        int ans = 0;
        for (int i = p; i >= 1; i -= i & -i) {
            ans += a[i];
        }
        return ans;
    }
} tree(N);

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n+1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= m; i++) {
        int l, r, x;
        cin >> l >> r >> x;
        b[l-1].push_back({i,x,-1});
        b[r].push_back({i,x,1});
    }
    vector<int> ans(m+1);
    for (int i = 1; i <= n; i++) {
        tree.ad(a[i],1);
        for (auto j : b[i]) {
            ans[j.id] += j.f * tree.qr(j.v);
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

F - Chord Crossing

考虑对于一个查询[l,r]有贡献, 其中必有一个点落在(l,r)内，另外一点落在两端
转换为二维数点问题，每个查询转换为(l,r)[1,x-1] 和 (l,r)[y+1,n] 内的点的个数

对于一个(x,y)， 要同时添加(y,x)

防止漏算一种情况

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define _ cout << "----------" << endl
#define int long long

const int N = 2e6 + 10;
struct bit {
    int n;
    vector<int> a;
    bit(int _n) : n(_n) { a.assign(n + 1, 0); }
    inline int lb(int x) { return x & -x; }
    void ad(int p, int x) { for (int i = p; i <= n; i += lb(i)) a[i] += x;}
    inline int qr(int p) {int ans=0; for(int i = p; i >= 1; i -= lb(i)) ans += a[i]; return ans;}
    inline int qr(int l, int r) {return qr(r) - qr(l-1);}
} tree(N);

struct nd {
    int l, r, id, f;
};

vector<nd> b[N];
vector<int> a[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    n *= 2;
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        a[l].push_back(r);
        a[r].push_back(l);
    }
    cin >> m;
    vector<int> ans(m+1);
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        b[l-1].push_back({1,l-1,i,-1});
        b[r].push_back({1,l-1,i,1});
        b[l-1].push_back({r+1,n,i,-1});
        b[r].push_back({r+1,n,i,1});
    }
    for (int i = 1; i <= n; i++) {
        for (auto j : a[i]) {
            tree.ad(j,1);
        }
        for (auto j : b[i]) {
            ans[j.id] += j.f * tree.qr(j.l,j.r);
        }
    }
    for (int i = 1; i <= m; i++) {
        cout << ans[i] << "\n"; 
    }
    return 0;
}