hdu 5618 Jam's problem again （cdq分治+BIT，三维偏序）

2017-10-10 · 2 min read · cdq分治 树状数组

题目链接

题意:

If two point such as (xi,yi,zi) and (xj,yj,zj) xi≥xj yi≥yj zi≥zj, the bigger one level add 1

问每个point的level是多少。

思路：

cdq分治，先去重并统计相同的点的数量，需要注意要记录原id对应到了哪个新id

/* ***********************************************
Author :111qqz
Created Time :2017年10月10日 星期二 19时53分38秒
File Name :5618.cpp
************************************************ */

 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define PB push_back
14#define fst first
15#define sec second
16#define lson l,m,rt<<1
17#define rson m+1,r,rt<<1|1
18#define ms(a,x) memset(a,x,sizeof(a))
19typedef long long LL;
20#define pi pair < int ,int >
21#define MP make_pair

  1using namespace std;
  2const double eps = 1E-8;
  3const int dx4[4]={1,0,0,-1};
  4const int dy4[4]={0,-1,1,0};
  5const int inf = 0x3f3f3f3f;
  6const int N=1E5+7;
  7int n;
  8struct point
  9{
 10    int x,y,z;
 11    int id;
 12    int cnt,sum;
 13    void input( int _id)
 14    {
 15    scanf("%d %d %d",&x,&y,&z);
 16    id=_id;
 17    }
 18    bool operator < (const point &b)const
 19    {
 20    if (x!=b.x) return x<b.x;
 21    if (y!=b.y) return y<b.y;
 22    return z<b.z;
 23    }
 24    bool operator !=(const point &b)const
 25    {
 26    return x!=b.x||y!=b.y||z!=b.z;
 27    }
 28}p[N];
 29struct BIT
 30{
 31    int n,t[N];
 32    void init( int _n)
 33    {
 34    n = _n;
 35    ms(t,0);
 36    }
 37    inline int lowbit(int x){ return x&(-x);}
 38    void update( int x,int delta)
 39    {
 40    for ( int i = x ; i <= n ; i+=lowbit(i)) t[i] +=delta;
 41    }
 42    int Sum( int x)
 43    {
 44    int ret = 0 ;
 45    for ( int i = x ; i >=1 ;  i-=lowbit(i)) ret+=t[i];
 46    return ret;
 47    }
 48}bit;
 49bool cmpcdq(point a,point b){return a.y<b.y;}
 50bool cmpid(point a,point b){return a.id < b.id;}
 51void cdq( int l,int r)
 52{
 53    if (l==r) return;
 54    int mid = (l+r)>>1;
 55    cdq(l,mid);
 56    cdq(mid+1,r);
 57    sort(p+l,p+mid+1,cmpcdq);
 58    sort(p+mid+1,p+r+1,cmpcdq);
 59    int j = l;
 60    for ( int i = mid + 1 ; i <= r ; i++)
 61    {
 62    for ( ; j <= mid && p[j].y <= p[i].y ; j++) bit.update(p[j].z,p[j].cnt);
 63    p[i].sum+=bit.Sum(p[i].z);
 64    }
 65    for ( int i = l ; i < j ; i++) bit.update(p[i].z,-p[i].cnt);
 66}
 67int tot;
 68int ans[N];
 69int id[N]; //记录原id对应到了哪个新id
 70int main()
 71{
 72    #ifndef  ONLINE_JUDGE 
 73    freopen("./in.txt","r",stdin);
 74  #endif
 75    int T;
 76    scanf("%d",&T);
 77    while (T--)
 78    {
 79        tot=0;
 80        ms(p,0); //多组数据orz
 81        scanf("%d",&n);
 82        bit.init(N-1);
 83        for ( int i = 1 ; i <= n ; i++) p[i].input(i);
 84        int cnt = 0;
 85        sort(p+1,p+n+1);
 86        for ( int i = 1 ; i <= n ; i++)
 87        {
 88        cnt++;
 89        if (p[i]!=p[i+1])
 90        {
 91            p[i].cnt = cnt;
 92            id[p[i].id]=tot+1;
 93            p[++tot]=p[i];
 94            p[tot].id = tot;
 95            cnt=0;
 96        }
 97        else
 98        {
 99            id[p[i].id] = tot+1;
100        }

1        }
2        cdq(1,tot);
3        //for ( int i = 1 ; i <= n ; i++)  ans[id[p[i].id]] = p[i].sum ;
4        //for ( int i = 1 ; i <= n ; i++) printf("%d\n",ans[i]);

1        sort(p+1,p+tot+1,cmpid);
2        for ( int i = 1 ; i <= n ; i++) printf("%d\n",p[id[i]].sum+p[id[i]].cnt-1);
3    }
4  #ifndef ONLINE_JUDGE  
5  fclose(stdin);
6  #endif
7    return 0;
8}