#include #include #include #include #include #include #include <">

日本搞逼视频_黄色一级片免费在线观看_色99久久_性明星video另类hd_欧美77_综合在线视频

國內(nèi)最全I(xiàn)T社區(qū)平臺 聯(lián)系我們 | 收藏本站
阿里云優(yōu)惠2
您當(dāng)前位置:首頁 > php框架 > codeigniter > cdq分治

cdq分治

來源:程序員人生   發(fā)布時間:2014-09-29 20:10:11 閱讀次數(shù):3832次

第一次遇到這種神奇的東西

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 ",ans.first,ans.second); } return 0; }


生活不易,碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
程序員人生
------分隔線----------------------------
分享到:
------分隔線----------------------------
關(guān)閉
程序員人生
主站蜘蛛池模板: 99视频观看| 神马久久精品 | www.夜夜操.com| 亚洲精品视频在线观看免费 | 亚洲第一视频 | 欧美日韩综合视频 | 久久免费一区 | 欧美成人a | 欧美伊人精品成人久久综合97 | 亚洲小视频 | 国产精品三级 | 精品视频一区二区 | 久久久久久美女 | 成人看片在线观看 | 久久99久久99 | 亚洲国产精品一区二区第一页 | 精品成人久久 | 视频三区| 伊人色婷婷 | 欧美成人精品一区 | 高潮av | 亚州男人天堂 | 亚洲视频精品在线 | 青草福利视频 | 午夜伦伦影理论片大片飘花影院 | 成人午夜网 | 成人免费视频在线观看 | 91色在线观看 | 精品三级久久久 | 精品国产91久久久久久 | 久久久久一区二区三区 | 亚洲精品综合一区二区 | 久久网站热最新地址 | 精品国产a | 黄色小视频免费 | 三级黄色网络 | 午夜久久精品 | 综合久久狠狠色成人网 | 欧美激情综合五月色丁香小说 | 一区二区激情 | 成人av在线网站 |