首页 > 代码库 > hdu_5324_Boring Class(cdq分治+树状数组)
hdu_5324_Boring Class(cdq分治+树状数组)
题目链接:hdu_5324_Boring Class
题意:
给出n个二维点对,求LIS长度和编号字典序最小的LIS(x非增,y非减)
题解:
dp[i]=max(dp[j]) (i>j,l[i]>=l[j],r[i]<=r[i])
一看就是三维偏序问题。
如果树套树写的好,空间开的大的话,一样可以过,不过这里还是用cdq分治套树状数组好写一点。
用lowbit来维护dp[j]的最大值,然后因为要字典序最小,所以从后往前dp。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 5 const int N=1e5+7; 6 7 int n,dp[N],hsh[N],ed,pre[N]; 8 9 struct BIT 10 { 11 int val,idx; 12 BIT(){val=0,idx=N;} 13 }bit[N],tp; 14 15 inline void up(BIT &a,BIT b){if(a.val<b.val||a.val==b.val&&a.idx>b.idx)a=b;} 16 inline void add(int x,BIT c){while(x<=n)up(bit[x],c),x+=x&-x;} 17 inline void clr(int x){while(x<=n)bit[x].val=0,bit[x].idx=N,x+=x&-x;} 18 inline BIT ask(int x){BIT ans;while(x)up(ans,bit[x]),x-=x&-x;return ans;} 19 20 struct node 21 { 22 int x,y,idx; 23 bool operator<(const node & b)const 24 { 25 if(y!=b.y)return y<b.y; 26 if(x!=b.x)return x>b.x; 27 return idx<b.idx; 28 } 29 }a[N],tmp[N]; 30 31 void cdq(int l,int r) 32 { 33 if(l==r)return; 34 int m=l+r>>1; 35 cdq(m+1,r); 36 F(i,l,r)tmp[i]=a[i]; 37 sort(tmp+l,tmp+m+1); 38 sort(tmp+m+1,tmp+r+1); 39 int j=r; 40 for(int i=m;i>=l;i--) 41 { 42 for(;j>m&&tmp[j].y>=tmp[i].y;j--) 43 { 44 tp.val=dp[tmp[j].idx],tp.idx=tmp[j].idx; 45 add(tmp[j].x,tp); 46 } 47 BIT an=ask(tmp[i].x); 48 if(dp[tmp[i].idx]<an.val+1)dp[tmp[i].idx]=an.val+1,pre[tmp[i].idx]=an.idx; 49 else if(dp[tmp[i].idx]==an.val+1)pre[tmp[i].idx]=min(pre[tmp[i].idx],an.idx); 50 } 51 F(i,m+1,r)clr(tmp[i].x); 52 cdq(l,m); 53 } 54 55 int main() 56 { 57 while(~scanf("%d",&n)) 58 { 59 F(i,1,n)scanf("%d",&a[i].x),a[i].idx=i,dp[i]=1,pre[i]=N; 60 F(i,1,n)scanf("%d",&a[i].y); 61 F(i,1,n)hsh[i]=a[i].x; 62 sort(hsh+1,hsh+1+n),ed=unique(hsh+1,hsh+1+n)-hsh; 63 F(i,1,n)a[i].x=lower_bound(hsh+1,hsh+1+ed,a[i].x)-hsh; 64 F(i,1,n)hsh[i]=a[i].y; 65 sort(hsh+1,hsh+1+n),ed=unique(hsh+1,hsh+1+n)-hsh; 66 F(i,1,n)a[i].y=lower_bound(hsh+1,hsh+1+ed,a[i].y)-hsh; 67 cdq(1,n); 68 int mx=0,st; 69 F(i,1,n)mx=max(mx,dp[i]); 70 F(i,1,n)if(mx==dp[i]){st=i;break;} 71 printf("%d\n",mx); 72 for(int i=st,cnt=0;i<=n;i=pre[i])printf("%d%c",i," \n"[++cnt==mx]); 73 } 74 return 0; 75 }
hdu_5324_Boring Class(cdq分治+树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。