树状数组套值域线段树

三维偏序

看到三维偏序,最简单直接的思路就是先按照$x$把元素排序,然后按顺序把每个元素放进二维数据结构,统计二维前缀和,即为$x$、$y$、$z$都不超过该元素的元素个数。

以下为二维线段树(树套树)代码

// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;
const int MAXK = 2e5;

int n, k, cnt[MAXN];

struct Data{
    int x, y, z;
    
    int operator < (const Data &o) const {
        return x != o.x ? (x < o.x) : (y != o.y ? (y < o.y) : (z < o.z));
    }
    
    int operator == (const Data &o) const {
        return x == o.x && y == o.y && z == o.z;
    }
}data[MAXN];

struct Seg{
    struct Node{
        int val;
        Node *ch[2];
        
        Node(int val = 0) : val(val) {
            ch[0] = ch[1] = NULL;
        }
    };
    
    Node *rt;
    
    Seg() {
        rt = NULL;
    }
    
    void Modify(Node *&now, int pos, int val = 1, int nl = 1, int nr = MAXK) {
        if (!now) now = new Node();
        if (nl == nr) {
            now->val += val;
            return;
        }
        int mid = nl + nr >> 1;
        if (pos <= mid) Modify(now->ch[0], pos, val, nl, mid);
        else Modify(now->ch[1], pos, val, mid + 1, nr);
        now->val = (now->ch[0] ? now->ch[0]->val : 0) + (now->ch[1] ? now->ch[1]->val : 0);
    }
    
    int Query(Node *now, int l, int r, int nl = 1, int nr = MAXK) {
        if (!now) return 0;
        if (l == nl && r == nr) return now->val;
        int mid = nl + nr >> 1;
        if (r <= mid) return Query(now->ch[0], l, r, nl, mid);
        else if (l > mid) return Query(now->ch[1], l, r, mid + 1, nr);
        return Query(now->ch[0], l, mid, nl, mid) + Query(now->ch[1], mid + 1, r, mid + 1, nr);
    }
};

Seg tree[MAXK * 4 + 5];

void Modify(int now, int posx, int posy, int val, int nl = 1, int nr = MAXK) {
    tree[now].Modify(tree[now].rt, posy, val);
    if (nl == nr) return;
    int mid = nl + nr >> 1;
    if (posx <= mid) Modify(now << 1, posx, posy, val, nl, mid);
    else Modify(now << 1 | 1, posx, posy, val, mid + 1, nr);
}

int Query(int now, int xl, int xr, int yl, int yr, int nl = 1, int nr = MAXK) {
    if (xl == nl && xr == nr) return tree[now].Query(tree[now].rt, yl, yr);
    int mid = nl + nr >> 1;
    if (xr <= mid) return Query(now << 1, xl, xr, yl, yr, nl, mid);
    else if (nl > mid) return Query(now << 1 | 1, xl, xr, yl, yr, mid + 1, nr);
    return Query(now << 1, xl, mid, yl, yr, nl, mid) + Query(now << 1 | 1, mid + 1, xr, yl, yr, mid + 1, nr);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> data[i].x >> data[i].y >> data[i].z;
    sort(data + 1, data + n + 1);
    int sum = 1;
    for (int i = 1; i <= n; i++) {
        if (data[i + 1] == data[i]) {
            sum++;
            continue;
        }
        Modify(1, data[i].y, data[i].z, sum);
        int res = Query(1, 1, data[i].y, 1, data[i].z);
        cnt[res] += sum;
        sum = 1;
    }
    for (int i = 1; i <= n; i++) cout << cnt[i] << endl;
    return 0;
}

Ctrl+CCtrl+v交上去,发现TLE70

考虑到值域不大,并且线段树常数较大,可以把外层的非动态开点线段树换成树状数组,减小常数,以下为AC代码。

// luogu-judger-enable-o2
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1e5 + 5;
const int MAXK = 2e5;

int n, k, cnt[MAXN];

struct Data{
    int x, y, z;
    
    int operator < (const Data &o) const {
        return x != o.x ? (x < o.x) : (y != o.y ? (y < o.y) : (z < o.z));
    }
    
    int operator == (const Data &o) const {
        return x == o.x && y == o.y && z == o.z;
    }
}data[MAXN];

struct Seg{
    struct Node{
        int val;
        Node *ch[2];
        
        Node(int val = 0) : val(val) {
            ch[0] = ch[1] = NULL;
        }
    };
    
    Node *rt;
    
    Seg() {
        rt = NULL;
    }
    
    void Modify(Node *&now, int pos, int val, int nl, int nr) {
        if (!now) now = new Node();
        if (nl == nr) {
            now->val += val;
            return;
        }
        int mid = nl + nr >> 1;
        if (pos <= mid) Modify(now->ch[0], pos, val, nl, mid);
        else Modify(now->ch[1], pos, val, mid + 1, nr);
        now->val = (now->ch[0] ? now->ch[0]->val : 0) + (now->ch[1] ? now->ch[1]->val : 0);
    }
    
    int Query(Node *now, int l, int r, int nl, int nr) {
        if (!now) return 0;
        if (l == nl && r == nr) return now->val;
        int mid = nl + nr >> 1;
        if (r <= mid) return Query(now->ch[0], l, r, nl, mid);
        else if (l > mid) return Query(now->ch[1], l, r, mid + 1, nr);
        return Query(now->ch[0], l, mid, nl, mid) + Query(now->ch[1], mid + 1, r, mid + 1, nr);
    }
};
/*
Seg tree[MAXK * 4 + 5];

void Modify(int now, int posx, int posy, int val, int nl = 1, int nr = MAXK) {
    tree[now].Modify(tree[now].rt, posy, val);
    if (nl == nr) return;
    int mid = nl + nr >> 1;
    if (posx <= mid) Modify(now << 1, posx, posy, val, nl, mid);
    else Modify(now << 1 | 1, posx, posy, val, mid + 1, nr);
}

int Query(int now, int xl, int xr, int yl, int yr, int nl = 1, int nr = MAXK) {
    if (xl == nl && xr == nr) return tree[now].Query(tree[now].rt, yl, yr);
    int mid = nl + nr >> 1;
    if (xr <= mid) return Query(now << 1, xl, xr, yl, yr, nl, mid);
    else if (nl > mid) return Query(now << 1 | 1, xl, xr, yl, yr, mid + 1, nr);
    return Query(now << 1, xl, mid, yl, yr, nl, mid) + Query(now << 1 | 1, mid + 1, xr, yl, yr, mid + 1, nr);
}
*/

Seg tree[MAXK + 5];

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

void Modify(int posx, int posy, int val) {
    for (int i = posx; i <= k; i += LB(i)) 
        tree[i].Modify(tree[i].rt, posy, val, 1, k);
}

int Query(int x, int y) {
    int ret = 0;
    for (int i = x; i; i -= LB(i)) ret += tree[i].Query(tree[i].rt, 1, y, 1, k);
    return ret;
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> data[i].x >> data[i].y >> data[i].z;
    sort(data + 1, data + n + 1);
    int sum = 1;
    for (int i = 1; i <= n; i++) {
        if (data[i + 1] == data[i]) {
            sum++;
            continue;
        }
        Modify(data[i].y, data[i].z, sum);
        int res = Query(data[i].y, data[i].z);
        cnt[res] += sum;
        sum = 1;
    }
    for (int i = 1; i <= n; i++) cout << cnt[i] << endl;
    return 0;
}