cdq分治

#include <cstring> #include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <queue> #include <string> #include <set> #include <stack> using namespace std; #define ll long long #define eps 1e-8 #define pi acos(-1.0) #define inf 0x3f3f3f3f #define mod (1<<30) #define sqr(x) ((x)*(x)) #define lson (u<<1) #define rson (u<<1|1) #define maxn 100011 #define maxm 4000100 #define mp(a,b) make_pair(a,b) #define pii pair<int,int> //#pragma comment(linker,"/STACK:102400000,102400000") int n,cnt,arr[maxn]; struct P{ int x,y,z,id; P(){} P(int _x,int _y,int _z) :x(_x),y(_y),z(_z){} void input(){ scanf("%d%d%d",&x,&y,&z); } bool operator<(const P& p) const{ if(x!=p.x) return x < p.x; if(y!=p.y) return y < p.y; return z < p.z; } }p[maxn],tmp[maxn]; pii dp[maxn],bit[maxn]; void update(pii& a,pii b){ if(a.first < b.first) a = b; else if(a.first == b.first) { a.second += b.second; if(a.second >= mod) a.second -= mod; } } void add(int idx,pii v){ for(int i=idx;i<=cnt;i+=i&(-i)){ update(bit[i],v); } } void clear(int idx){ for(int i=idx;i<=cnt;i+=i&(-i)) bit[i] = mp(0,0); } pii query(int idx){ pii ret = mp(0,0); for(int i=idx;i>0;i-=i&(-i)) update(ret,bit[i]); return ret; } void gao(int l,int r){ if(l>=r) return ; int mid = (l+r)>>1; gao(l,mid); int xx = 0; for(int i=l;i<=r;i++){ tmp[xx] = p[i]; tmp[xx++].x = 0; } sort(tmp,tmp+xx); for(int i=0;i<xx;i++){ if(tmp[i].id<=mid){ add(tmp[i].z,dp[tmp[i].id]); } else{ pii tt = query(tmp[i].z); tt.first++; update(dp[tmp[i].id],tt); } } for(int i=0;i<xx;i++){ if(tmp[i].id<=mid) clear(tmp[i].z); } gao(mid+1,r); } int main() { int T; scanf("%d",&T); while(T--){ scanf("%d",&n); cnt = 0; for(int i=1;i<=n;i++){ p[i].input(); arr[cnt++] = p[i].z; dp[i] = mp(1,1); } sort(p+1,p+1+n); sort(arr,arr+cnt); cnt = unique(arr,arr+cnt)-arr; for(int i=1;i<=n;i++) { p[i].id = i; p[i].z = lower_bound(arr,arr+cnt,p[i].z)-arr+1; } for(int i=0;i<=cnt;i++) bit[i] = mp(0,0); gao(1,n); pii ans = mp(0,0); for(int i=1;i<=n;i++) update(ans,dp[i]); printf("%d %d ",ans.first,ans.second); } return 0; }