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

2017年10月10日 0 作者 CrazyKK

题目链接

题意:

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

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
 
 
/* ***********************************************
Author :111qqz
Created Time :2017年10月10日 星期二 19时53分38秒
File Name :5618.cpp
************************************************ */
 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
 
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int n;
struct point
{
    int x,y,z;
    int id;
    int cnt,sum;
    void input( int _id)
    {
    scanf("%d %d %d",&x,&y,&z);
    id=_id;
    }
    bool operator < (const point &b)const
    {
    if (x!=b.x) return x<b.x;
    if (y!=b.y) return y<b.y;
    return z<b.z;
    }
    bool operator !=(const point &b)const
    {
    return x!=b.x||y!=b.y||z!=b.z;
    }
}p[N];
struct BIT
{
    int n,t[N];
    void init( int _n)
    {
    n = _n;
    ms(t,0);
    }
    inline int lowbit(int x){ return x&(-x);}
    void update( int x,int delta)
    {
    for ( int i = x ; i <= n ; i+=lowbit(i)) t[i] +=delta;
    }
    int Sum( int x)
    {
    int ret = 0 ;
    for ( int i = x ; i >=1 ;  i-=lowbit(i)) ret+=t[i];
    return ret;
    }
}bit;
bool cmpcdq(point a,point b){return a.y<b.y;}
bool cmpid(point a,point b){return a.id < b.id;}
void cdq( int l,int r)
{
    if (l==r) return;
    int mid = (l+r)>>1;
    cdq(l,mid);
    cdq(mid+1,r);
    sort(p+l,p+mid+1,cmpcdq);
    sort(p+mid+1,p+r+1,cmpcdq);
    int j = l;
    for ( int i = mid + 1 ; i <= r ; i++)
    {
    for ( ; j <= mid && p[j].y <= p[i].y ; j++) bit.update(p[j].z,p[j].cnt);
    p[i].sum+=bit.Sum(p[i].z);
    }
    for ( int i = l ; i < j ; i++) bit.update(p[i].z,-p[i].cnt);
}
int tot;
int ans[N];
int id[N]; //记录原id对应到了哪个新id
int main()
{
    #ifndef  ONLINE_JUDGE
    freopen("./in.txt","r",stdin);
  #endif
    int T;
    scanf("%d",&T);
    while (T--)
    {
        tot=0;
        ms(p,0); //多组数据orz
        scanf("%d",&n);
        bit.init(N-1);
        for ( int i = 1 ; i <= n ; i++) p[i].input(i);
        int cnt = 0;
        sort(p+1,p+n+1);
        for ( int i = 1 ; i <= n ; i++)
        {
        cnt++;
        if (p[i]!=p[i+1])
        {
            p[i].cnt = cnt;
            id[p[i].id]=tot+1;
            p[++tot]=p[i];
            p[tot].id = tot;
            cnt=0;
        }
        else
        {
            id[p[i].id] = tot+1;
        }
 
        }
        cdq(1,tot);
        //for ( int i = 1 ; i <= n ; i++)  ans[id[p[i].id]] = p[i].sum ;
        //for ( int i = 1 ; i <= n ; i++) printf("%d\n",ans[i]);
        
        sort(p+1,p+tot+1,cmpid);
        for ( int i = 1 ; i <= n ; i++) printf("%d\n",p[id[i]].sum+p[id[i]].cnt-1);
    }
  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}
 
 
 
 

 

分类目录hdoj
标签cdq分治 树状数组

关于作者

ex-ACMer@hust，stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人！

提醒
wpDiscuz