社区讨论
为何同一份代码在洛谷样例 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 条回复,欢迎继续交流。
正在加载回复...