P3810 -三维偏序（陌上花开）cdq-分治

• P3810 【模板】三维偏序（陌上花开）

• 思路 :按照 1维排序 二维 分治三维树状数组维护。

• #include<bits/stdc++.h>
  using namespace std;
  #define maxn 234567
  int n,k,id,s,tree[maxn*2],tong[maxn];
  struct node
  {
      int a,b,c,ans,w;
      node()
      {
          ans=0;
          w=0;
      }
  } data[maxn];
  bool cp1(node x,node y)
  {
      if(x.a!=y.a)
          return x.a<y.a;
      if(x.b!=y.b)
          return x.b<y.b;
      if(x.c!=y.c)
          return x.c<y.c;
  }
  bool cp(node x,node y)
  {
      return x.b<y.b;
  }
  void add(int po,int ad)
  {
      while(po<=k)
      {
          tree[po]+=ad;
          po+=po&-po;
      }
  }
  int query(int po)
  {
      int ret=0;
      while(po)
      {
          ret+=tree[po];
          po-=po&-po;
      }
      return ret;
  }
  void cdq(int l,int r)
  {
      if(l>=r)return ;
      int mid=(l+r)>>1;
      cdq(l,mid);
      cdq(mid+1,r);
      sort(data+l,data+1+mid,cp);
      sort(data+1+mid,data+1+r,cp);
      int i=l,j=mid+1;
      for(; j<=r; j++)
      {
          while(data[i].b<=data[j].b&&i<=mid)
          {
              add(data[i].c,data[i].w);
              i++;
          }
          data[j].ans+=query(data[j].c);
      }
      for(j=l; j<i; j++)
          add(data[j].c,-data[j].w);
  }
  int main()
  {
      scanf("%d%d",&n,&k);
      for(int i=1; i<=n; i++)
          scanf("%d%d%d",&data[i].a,&data[i].b,&data[i].c);
      sort(data+1,data+1+n,cp1);
      for(int i=1; i<=n; i++)
      {
          s++;
          if(data[i].a!=data[i+1].a||data[i].b!=data[i+1].b||data[i].c!=data[i+1].c)
              data[++id]=data[i],data[id].w=s,s=0;
      }
      cdq(1,id);
      for(int i=1; i<=id; i++)
          tong[data[i].ans+data[i].w-1]+=data[i].w;
      for(int i=0; i<n; i++)printf("%d\n",tong[i]);
      return 0;
  }