HDU4742 CDQ分治，三维LIS

HDU4742 CDQ分治，三维LIS

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=4742

题意：

每个球都有三个属性值x,y,z，要求最长的lis的长度和方案数

题解：

一维LIS很好求，dp一下就行

二维的LIS，将第一维排序后，和第一维一样

那么三维的lis怎么做了，我们很容易想到将第一维排序后分治的写，分了后， 按照y排序，怎么治呢？用树状数组更新前前x的最大值，然后再用dp更新即可

这里需要注意，和陌上花开等板子题不一样，我们这里不能分了左半部分后再直接分右半部分，这个地方卡了我好久。这里的分治运用是用来给dp服务的，我们dp是由前面的状态转移过来，所以，我们要先更新左半边后再去分治右半边

代码：

#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define bug printf("*********
")
#define FIN freopen("input.txt","r",stdin);
#define FON freopen("output.txt","w+",stdout);
#define IO ios::sync_with_stdio(false),cin.tie(0)
#define debug1(x) cout<<"["<<#x<<" "<<(x)<<"]
"
#define debug2(x,y) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<"]
"
#define debug3(x,y,z) cout<<"["<<#x<<" "<<(x)<<" "<<#y<<" "<<(y)<<" "<<#z<<" "<<z<<"]
"
const int maxn = 3e5 + 5;
const int  mod = 1 << 30;
int n;
struct P {
    int x, y, z, id;
} point[maxn], now[maxn];
struct A {
    int max, sum;
} ans[maxn], tr[maxn];
bool cmpx(const P a, const P b) {
    return a.x < b.x;
}
bool cmpy(const P a, const P b) {
    return a.y < b.y;
}
bool cmpz(const P a, const P b) {
    return a.z < b.z;
}

int lowbit(int x) {
    return (x & -x);
}

void insert(int x, A tmp) {
    for(int i = x; i <= n; i += lowbit(i)) {
        if(tr[i].max == tmp.max) {
            tr[i].sum += tmp.sum;
            tr[i].sum %= mod;
        } else if(tr[i].max < tmp.max) {
            tr[i].sum = tmp.sum;
            tr[i].max = tmp.max;
        }
    }
}

A getsum(int x) {
    A ret;
    ret.max = -1;
    for(int i = x; i >= 1; i -= lowbit(i)) {
        if(tr[i].max > ret.max) {
            ret.max = tr[i].max;
            ret.sum = tr[i].sum;
        } else if(tr[i].max == ret.max) {
            ret.sum += tr[i].sum;
            ret.sum %= mod;
        }
    }
    return ret;
}

void clear(int x) {
    for(int i = x; i <= n; i += lowbit(i)) {
        tr[i].max = 0;
        tr[i].sum = 0;
    }
}

void solve(int l, int r) {
    if(l == r) return ;
    int mid = l + r >> 1;
    solve(l, mid);
    for(int i = mid + 1; i <= r; i++)
        now[i] = point[i];
    sort(point + l, point + mid + 1, cmpz);
    sort(point + mid + 1, point + r + 1, cmpz);
    for(int i = mid + 1, top = l; i <= r; i++) {
        while(top <= mid && point[top].z <= point[i].z) {
            insert(point[top].x, ans[point[top].id]);
            top++;
        }
        A ret = getsum(point[i].x);
        ret.max++;
        if(ret.max == ans[point[i].id].max) {
            ans[point[i].id].sum += ret.sum;
            ans[point[i].id].sum %= mod;
        } else if(ret.max > ans[point[i].id].max) {
            ans[point[i].id] = ret;
        }
    }
    for(int i = l; i <= mid; i++) clear(point[i].x);
    for(int i = mid + 1; i <= r; i++)
        point[i] = now[i];


    solve(mid + 1, r);
}
//dp[i]=max(dp[i-1],dp[j]+1)
int main() {
#ifndef ONLINE_JUDGE
    FIN
#endif
    int T;
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d %d %d", &point[i].x, &point[i].y, &point[i].z);
            point[i].id = i;
        }
        sort(point + 1, point + 1 + n, cmpx);
        for(int i = 1, xx = point[1].x - 1, num = 0; i <= n; i++) {
            if(point[i].x != xx) num++, xx = point[i].x;
            point[i].x = num;
        }
        sort(point + 1, point + 1 + n, cmpy);

        for(int i = 1; i <= n; i++) {
            ans[i].max = 1;
            ans[i].sum = 1;
        }
        solve(1, n);
        A ret;
        ret.max = -1;
        for(int i = 1; i <= n; i++) {
            if(ret.max == ans[i].max) {
                ret.sum += ans[i].sum;
                ret.sum %= mod;
            } else if(ret.max < ans[i].max) {
                ret = ans[i];
            }
        }
        printf("%d %d
", ret.max, ret.sum);
    }
    return 0;
}