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
#include
#include
#include
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 xb;
}
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=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;
}