AT_joisc2019_a 試験 (Examination) 题解

题目链接：試験 (Examination)

题意：

有 \(n\) 个二元组 \((a,b)\) 和 \(q\) 个询问 \((x,y,z)\) 。

每个询问求满足 \(a\ge x,~b\ge y,~a+b\ge z\)​ 的二元组个数。

数据范围：

\(1\le n,q\le 10^5,~0 \le a,b,x,y\le 10^9,~0 \le z\le 2\times 10^9\)。

令 \(c = a + b\) ，那么问题就变成了，对于询问 \((x,y,z)\) ，求满足 \[ a \ge x,~b \ge y,~c \ge z \] 的三元组 \((a,b,c)\) 的个数。

不过这道题 \(c,z\)​ 都非常大，需要离散化一下。

时间复杂度 \(\mathcal{O}(n\log^2 n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 55))

int n, tot, len, tmp[N], ans[N], tr[N];
struct node { int op, x, y, z, id; } a[N];
// 注意相等的时候要按时间戳排序，否则加点可能排到询问的后面！！
bool cmpx(node x, node y) { return x.x == y.x ? x.id < y.id : x.x > y.x; }
bool cmpy(node x, node y) { return x.y == y.y ? x.id < y.id : x.y > y.y; }
int lowbit(int x) { return x & (-x); }
void add(int x, int v) { for(int i = x; i; i -= lowbit(i)) tr[i] += v; }
int qry(int x, int r = 0) { for(int i = x; i <= len; i += lowbit(i)) r += tr[i]; return r; }
void cdq(int l, int r)
{
    if(l == r) return;
    int mid = (l + r) >> 1; cdq(l, mid); cdq(mid + 1, r);
    sort(a + l, a + 1 + mid, cmpy); sort(a + 1 + mid, a + 1 + r, cmpy);
    int j = l;
    for(int i = mid + 1; i <= r; i++)
    {
        for(; a[j].y >= a[i].y && j <= mid; j++) if(a[j].op == 1) add(a[j].z, 1);
        if(a[i].op == 2) ans[a[i].id] += qry(a[i].z);
    }
    for(int i = l; i < j; i++) if(a[i].op == 1) add(a[i].z, -1);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int q; cin >> n >> q;
    for(int i = 1, x, y; i <= n; i++) { 
        cin >> x >> y; a[++tot] = {1, x, y, x + y, 0}; tmp[tot] = x + y;
    }
    for(int i = 1, x, y, z; i <= q; i++) {
        cin >> x >> y >> z; a[++tot] = {2, x, y, z, i}; tmp[tot] = z;
    }
    sort(tmp + 1, tmp + 1 + tot);
    len = unique(tmp + 1, tmp + 1 + tot) - tmp - 1;
    for(int i = 1; i <= tot; i++)
        a[i].z = lower_bound(tmp + 1, tmp + 1 + len, a[i].z) - tmp; 
    sort(a + 1, a + 1 + tot, cmpx);
    cdq(1, tot); for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}

---

题外话：

板子题不想放图片。