首页 > 代码库 > cdq分治
cdq分治
第一次遇到这种神奇的东西
hdu4742
#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\n",ans.first,ans.second); } return 0; }
cdq分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。