社区讨论
求助:windows本机能过,洛谷ide死活过不了。
P3810【模板】三维偏序 / 陌上花开参与者 2已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6tdyrz
- 此快照首次捕获于
- 2025/11/20 10:30 4 个月前
- 此快照最后确认于
- 2025/11/20 10:30 4 个月前
一直wa两个点。局部变量都有初值
蒟蒻附上自己代码(虽然有点丑
CPP#include<bits/stdc++.h>
#define maxn 100010
#define lowbit(x) (x&(-x))
using namespace std;
int tot1,tot2,tot,last,num,gs[maxn],t[maxn*3];
struct ooxx{
int a,b,c,sum,cnt;
}a[maxn],c[maxn];
inline bool same(ooxx em,ooxx emm) {return ((em.a==emm.a)&&(em.b==emm.b)&&(em.c==emm.c));}
inline bool cmp(ooxx em,ooxx emm)
{
if (em.a!=emm.a) return em.a<emm.a;
if (em.b!=emm.b) return em.b<emm.b;
return em.c<emm.c;
}
inline void insert(int pos,int d)
{
for (;pos<=maxn*3-1;pos+=lowbit(pos)) t[pos]+=d;
}
inline void modify(int pos)
{
for (;pos<=maxn*3-1;pos+=lowbit(pos)) t[pos]=0;
}
inline int query(int pos)
{
int ret=0;
for (;pos>0;pos-=lowbit(pos)) ret+=t[pos];
return ret;
}
inline void merge(int l,int r)
{
int mid=(l+r)>>1;
last=0;
tot1=l,tot2=mid+1;
while (last<=r-l+1)
{
if (tot1<=mid&&(tot2>r|a[tot1].b<=a[tot2].b)) c[++last]=a[tot1],insert(c[last].c,c[last].cnt),tot1++;
else c[++last]=a[tot2],c[last].sum=c[last].sum+query(c[last].c),tot2++;
}
mid=0;
for (int i=l;i<=r;++i) ++mid,modify(a[i].c),a[i]=c[mid];
}
inline void solve(int l,int r)
{
if (l==r) return;
int mid=(l+r)>>1;
solve(l,mid),solve(mid+1,r),merge(l,r);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;++i) scanf("%d%d%d",&a[i].a,&a[i].b,&a[i].c);
sort(a+1,a+n+1,cmp),last=num=1;
for (int i=1;i<=n;++i)
{
if (!same(a[last],a[i]))
{
for (int j=last+1;j<i;++j) a[j].a=maxn*99;
last=i,num++;
}
a[last].cnt++,a[last].sum=a[last].cnt-1;
}
sort(a+1,a+n+1,cmp);
solve(1,num);
for (int i=1;i<=num;++i) /*printf("%d %d %d %d %d\n",a[i].a,a[i].b,a[i].c,a[i].cnt,a[i].sum),*/gs[a[i].sum]+=a[i].cnt;
for (int i=0;i<n;++i) printf("%d\n",gs[i]);
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...