首页 > 代码库 > hdu4742

hdu4742

2024-07-25 12:47:29   206人阅读

题意：给定3维的n（<=100000）个点，求最长不下降子序列长度(对于1和2两个点，2可以放在1后面，x1<=x2,y1<=y2,z1<=z2 )，并求出有多少种方案。

思路：裸的cdq分治。。

         首先可以先对x排序，就降成二维了。。

         定义solve（l,r）为处理[l,r]的区间

         那么solve（l，r）为如下：{

                solve（l, mid）

                对于l,r的点按照y关键字排序

                然后从左到右（y增大方向）扫描，对于（l, mid）的点插入将值插入z离散化的数据结构里维护，

                对于（mid+1，r）的点直接查询数据结果，更改结果

                清空数据结构。

               solve（mid+1， r）

        }

       大致就这样，可以做到nlog^2n的复杂度。。数据结构可以选用bit或者线段树。。不过大家都选用bit吧。。

       cdq果然强大，还需慢慢体会呀。。

  1 /*  2  * Author:  Yzcstc  3  * Created Time:  2014年10月03日 星期五 22时57分13秒  4  * File Name: hdu4742.cpp  5  */  6 #include <iostream>  7 #include <cstdio>  8 #include <cstdlib>  9 #include <cstring> 10 #include <cmath> 11 #include <algorithm> 12 #include <string> 13 #include <vector> 14 #include <stack> 15 #include <queue> 16 #include <set> 17 #include <utility> 18 #define M0(x) memset(x, 0, sizeof(x)) 19 #define MP make_pair 20 #define PB push_back 21 #define repf(i, a, b) for (int i = (a); i <= (b); ++i) 22 #define Inf 0x3fffffff 23 #define eps 1e-8 24 #define pi acos(-1) 25 #define maxn 120000 26 #define X first 27 #define Y second 28 using namespace std; 29 typedef pair<int, int> pii; 30 struct point{ 31     int x, y, z,id; 32     void input(){ 33         scanf("%d%d%d", &x, &y, &z); 34     } 35     bool operator<(const point& p) const{ 36         if (x < p.x) return true; 37         if (x == p.x && y < p.y) return true; 38         if (x == p.x && y == p.y && z < p.z) return true; 39         return false; 40     } 41 } p[maxn], pt[maxn]; 42 int t[maxn], n, m; 43 pii dp[maxn], v[maxn], zero(0, 0); 44  45 void init(){ 46      scanf("%d", &n); 47      for (int i = 1; i <= n; ++i) 48           p[i].input(), t[i-1] = p[i].z; 49      sort(p + 1, p + 1 + n); 50      sort(t, t + n); 51      m = unique(t, t + n) - t; 52 //     cout << m << endl; 53      for (int i = 1; i <= n; ++i) 54           p[i].z = lower_bound(t, t + m, p[i].z) - t + 1; 55 //     repf(i, 1, n) printf("%d\n" ,p[i].z); 56      for (int i = 1; i <= n; ++i) 57           p[i].id = i; 58 } 59  60 /** BIT **/ 61 inline int lowbit(const int& x){ 62      return x & (-x);  63 } 64  65 inline void update(pii &a, const pii &b){ 66      if (a.X < b.X) a = b; 67      else if (a.X == b.X) a.Y += b.Y; 68 } 69  70 void modify(int x, const pii& val){ 71      for ( ; x <= m; x += lowbit(x)) 72          update(v[x], val); 73 } 74  75 pii query(int x){ 76      pii ret(0, 0); 77      for ( ; x > 0 ; x -= lowbit(x)) 78           update(ret, v[x]); 79      return ret; 80 } 81  82 void recover(int x){ 83      for (; x <= m; x += lowbit(x)) 84           v[x] = zero; 85 } 86 /** BIT-end **/ 87 /** Divide and conquer**/ 88 pii tmp; 89 void solve(const int& l,const int& r){ 90      if (l == r) return; 91      int mid = (l + r) >> 1; 92      solve(l, mid); 93      int sz = 0; 94      for (int i = l; i <= r; ++i) 95          pt[sz] = p[i], pt[sz++].x = 0; 96      sort(pt, pt+sz); 97      for (int i = 0; i < sz; ++i) 98          if (pt[i].id <= mid) 99                modify(pt[i].z, dp[pt[i].id]);100          else 101                tmp = query(pt[i].z), ++tmp.X, update(dp[pt[i].id], tmp);102      for (int i = 0; i < sz; ++i)103          if (pt[i].id <= mid)104                recover(pt[i].z);105      solve(mid + 1, r); 106 }107 108 void solve(){109      for (int i = 1; i <= n; ++i)110           dp[i].X = dp[i].Y = 1;111      solve(1, n);112      pii ans(0, 0);113      for (int i = 1; i <= n; ++i)114          update(ans, dp[i]); // printf("i = %d: %d %d\n", i, dp[i].first, dp[i].second);115      printf("%d %d\n", ans.X, ans.Y);116 }117 118 int main(){119  //   freopen("a.in", "r", stdin);120 //    freopen("a.out", "w", stdout);121     int cas;122     scanf("%d", &cas);123     while (cas--){124          init();125          solve(); 126     }127     return 0;128 }
View Code

 

             

 

hdu4742


联系
我们