社区讨论

求助: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 条回复,欢迎继续交流。

正在加载回复...