Hdu4742 （CDQ分治）

#include<cstdio>
#include<algorithm>
#define mid ((l + r) >> 1)
#define mp(a, b) make_pair(a, b)
#define    fi first
#define se second
using namespace std;
const int N = 1e5 + 5;

typedef pair<int, int> pii;

int t, n, x, y, z, len;
int kk[N];
pii dp[N], c[N];

struct Point{
    int x, y, z, id;
}p[N], temp[N];

bool cmp1(const Point &a, const Point &b) { return a.x < b.x; }

bool cmp2(const Point &a, const Point &b) { return a.y < b.y; }

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

pii ask(int x){
    pii ans = mp(0, 0);
    while(x){
        if(c[x].fi > ans.fi)  ans = c[x];
        else if(c[x].fi == ans.fi)  ans.se += c[x].se;
        x -= lowbit(x);  
    }
    return ans;
}

void modify(int x, pii k){
    while(x <= len){
        if(c[x].fi < k.fi)  c[x] = k;
        else if(c[x].fi == k.fi)  c[x].se += k.se;
        x += lowbit(x);
    }
}

void clear(int x){
    while(x <= len){
        c[x] = mp(0, 0);
        x += lowbit(x);
    }
}

void CDQ(int l, int r){
    if(l == r)  return ;
    CDQ(l, mid);
    for(int i = l; i <= r; ++i)  temp[i] = p[i];
    sort(temp + l, temp + r + 1, cmp2);
    for(int i = l; i <= r; ++i){
        if(temp[i].id > mid){
            int id = temp[i].id;
            pii q = ask(temp[i].z);
            ++q.first; 
            if(dp[id].fi < q.fi)  dp[id] = q;
            else if(dp[id].fi == q.fi)  dp[id].se += q.se;
        }
        else    modify(temp[i].z, dp[temp[i].id]);
    }
    for(int i = l; i <= r; ++i)  if(temp[i].id <= mid) clear(temp[i].z);
    CDQ(mid + 1, r);  
}

int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)     dp[i].fi = dp[i].se = 1;
        for(int i = 1; i <= n; ++i){
            scanf("%d%d%d", &x, &y, &z);
            p[i] = Point{x, y, z, i};
            kk[i] = z;
        }
        sort(p + 1, p + 1 + n, cmp1);
        sort(kk + 1, kk + 1 + n);
        len = unique(kk + 1, kk + 1 + n) - kk - 1;
        for(int i = 1; i <= n; ++i)  p[i].z = lower_bound(kk + 1, kk + 1 + len, p[i].z) - kk,  p[i].id = i;
        CDQ(1, n);
        pii ans = mp(0, 0);
        for(int i = 1; i <= n; ++i){
            if(dp[i].fi > ans.fi)   ans = dp[i];
            else if(dp[i].fi == ans.fi)  ans.se += dp[i].se;
        }
        printf("%d %d
", ans.fi, ans.se);
    }
    return 0;
}