社区讨论

为何同一份代码在洛谷样例 AC,在 dev-c++ 样例 RE

P3810【模板】三维偏序 / 陌上花开参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@mjbead5h
此快照首次捕获于
2025/12/18 20:06
2 个月前
此快照最后确认于
2025/12/20 19:00
2 个月前
查看原帖
rt
CPP
#include <bits/stdc++.h>
#define N 100010
#define K 200010
#define lowbit(x) (x & -x)
using namespace std;
int n, k, ans[N], realans[N], realn;
struct node {
    int id, a, b, c, cnt;
    bool operator !=(const node &x) const &{
        if(a != x.a) return 1;
        if(b != x.b) return 1;
        if(c != x.c) return 1;
        return 0;
    }
} s1[N], s[N];
struct FenwickTree {
    int fn, fw[K]; // fw yzm [笑哭]
    FenwickTree(int fn_) : fn(fn_) {for(int i = 1; i <= fn; i++) fw[i] = 0;}
    void update(int vis, int num) {for(; vis <= fn; vis += lowbit(vis)) fw[vis] += num;}
    int query(int vis) {int ret = 0; for(; vis; vis -= lowbit(vis)) ret += fw[vis]; return ret;}
};
bool cmp1(const node &x, const node &y) {
    if(x.a != y.a) return x.a < y.a;
    if(x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}
bool cmp2(const node &x, const node &y) {
    if(x.b != y.b) return x.b < y.b;
    return x.c < y.c;
}
void merge(int l, int r) {
    int mid = l + r >> 1;
    int itl = l, itr = mid + 1, tcnt = 0;
    node sorted[N];
    while(itl <= mid && itr <= r) {
        if(cmp2(s[itl], s[itr])) sorted[++tcnt] = s[itl++];
        else sorted[++tcnt] = s[itr++];
    }
    while(itl <= mid) sorted[++tcnt] = s[itl++];
    while(itr <= r) sorted[++tcnt] = s[itr++];
    for(int i = 1; i <= tcnt; i++) s[i + l - 1] = sorted[i];
}
void cdq(int l, int r) {
    if(l == r) return;
    int mid = l + r >> 1;
    cdq(l, mid); cdq(mid + 1, r);
    merge(l, mid); merge(mid + 1, r);
    FenwickTree FT(k);
    int itl = l;
    for(int itr = mid + 1; itr <= r; itr++) {
        while(itl <= mid && s[itl].b <= s[itr].b) {FT.update(s[itl].c, s[itl].cnt); itl++;}
        ans[s[itr].id] += FT.query(s[itr].c);
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> s1[i].a >> s1[i].b >> s1[i].c;
        s1[i].id = i;
        s1[i].cnt = 1;
    }
    sort(s1 + 1, s1 + n + 1, cmp1);
    for(int i = 1; i <= n; i++)
        if(i == 1 || s1[i] != s1[i - 1]) {s[++realn].id = realn; s[realn] = s1[i];}
        else s[realn].cnt++;
    cdq(1, realn);
    for(int i = 1; i <= realn; i++) realans[ans[s[i].id] + s[i].cnt - 1] += s[i].cnt;
    for(int i = 0; i < n; i++) cout << realans[i] << '\n';
    return 0;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...