首页 > 代码库 > UvaLive 6667 Longest Chain (分治求三元组LIS&树状数组)
UvaLive 6667 Longest Chain (分治求三元组LIS&树状数组)
题目链接:
here
题意:
和hdu4742类似。区别就是一部分三元组是直接给出的。还有一部分是用他给的那个函数生成的。还有就是这里的大于是严格的大于a>b必须ax>bx,ay>by,az>bz。
思路:
思路也和hdu4742here类似。只是有几个比较棘手的问题。现在变成严格大于了。对于y还是很好办的。我们在排序y的时候可以使的标号大的排在前面这样就可以防止y和它一样的更新它了。感觉比较麻烦的是x一样怎么办。这个真没想出什么好办法。就只有x和mid+1的x不一样的建一个树状数组bv。然后所有的不管一不一样再建个树状数组av。这样。遇到x等于mid+1的就用bv更新。其它的用av更新就好了。
详细见代码:
#include<algorithm> #include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int INF=0x3f3f3f3f; const int maxn=300030; typedef long long ll; struct node { int x,y,z; inline bool operator <(const node& tt) const { if(x!=tt.x) return x<tt.x; if(y!=tt.y) return y<tt.y; return z<tt.z; } } po[maxn]; int dp[maxn],sy[maxn],sz[maxn],av[maxn],bv[maxn],ans; int tmp[maxn<<1],ty[maxn],ptr; bool cmp(int a,int b) { if(po[a].y!=po[b].y) return po[a].y<po[b].y; return a>b; } void update(int mv[],int x,int v,int mn) { for(int i=x;i<=mn;i+=i&-i) mv[i]=max(mv[i],v); } int qu(int mv[],int x) { int ret=0; for(int i=x;i>0;i-=i&-i) ret=max(ret,mv[i]); return ret; } void solve(int l,int r) { if(l==r) { ans=max(ans,dp[l]); sz[l]=po[l].z; return; } int mid=(l+r)>>1,le=l,ri=mid+1,len=r-l+1,ml=mid-l+1,lim,h,i; memmove(tmp+ptr,sy+l,len*sizeof(int)); for(i=0;i<len;i++) if(tmp[ptr+i]<=mid)//直接把排好的序划分下去就行了。 sy[le++]=tmp[ptr+i]; else sy[ri++]=tmp[ptr+i]; ptr+=len; solve(l,mid); lim=ptr,ptr-=len; for(i=1;i<=ml;i++) av[i]=bv[i]=0; for(i=ptr;i<lim;i++) { if(tmp[i]<=mid) { h=lower_bound(sz+l,sz+l+ml,po[tmp[i]].z)-(sz+l)+1; update(av,h,dp[tmp[i]],ml); if(po[tmp[i]].x!=po[mid+1].x) update(bv,h,dp[tmp[i]],ml); continue; } h=lower_bound(sz+l,sz+l+ml,po[tmp[i]].z-1)-(sz+l); if(h>=ml||sz[l+h]>po[tmp[i]].z-1) h--; if(h>=0) { int *mv=po[tmp[i]].x==po[mid+1].x?bv:av; dp[tmp[i]]=max(dp[tmp[i]],qu(mv,h+1)+1); } } solve(mid+1,r); merge(sz+l,sz+l+ml,sz+l+ml,sz+l+len,ty); memmove(sz+l,ty,len*sizeof(int)); } int A,B,C = ~(1<<31),M = (1<<16)-1; int rd() { A = 36969 * (A & M) + (A >> 16); B = 18000 * (B & M) + (B >> 16); return (C & ((A << 16) + B)) % 1000000; } int main() { int m,n,i; while(scanf("%d%d%d%d",&n,&m,&A,&B),m||n||A||B) { for(i=1;i<=n;i++) scanf("%d%d%d",&po[i].x,&po[i].y,&po[i].z); for(i=n+1,n+=m;i<=n;i++) po[i].x=rd(),po[i].y=rd(),po[i].z=rd(); ptr=ans=0; sort(po+1,po+n+1); for(i=1;i<=n;i++) sy[i]=i,dp[i]=1; sort(sy+1,sy+n+1,cmp); solve(1,n); printf("%d\n",ans); } return 0; }
UvaLive 6667 Longest Chain (分治求三元组LIS&树状数组)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。