UvaLive 6667 Longest Chain (分治求三維LIS)
來(lái)源：程序員人生 發(fā)布時(shí)間：2014-10-03 08:00:01 閱讀次數(shù)：2882次
題目大意：
題目給出了定義的小于號(hào)，然后求出一個(gè)LIS。。。
思路分析：
這道題目的是一個(gè)嚴(yán)格遞增的，和 Hdu 4742 類(lèi)似。只不過(guò)Hdu的這道題是一個(gè)不遞減的序列。
簡(jiǎn)單說(shuō)一下Hdu 4742的做法。
首先我們可以想到的是一維的LIS，那么簡(jiǎn)單就是n。
然后二維的LIS，就是先排序一維，然后用求第二維的LIS。
現(xiàn)在問(wèn)題擴(kuò)展到三維。依然排序一維。
假設(shè)我們排序的是z。
然后記下排序后的id。現(xiàn)在已知，id小的z就小。
然后開(kāi)始分治，類(lèi)似線段樹(shù)的遞歸。對(duì)于一個(gè)區(qū)間，我們將這個(gè)區(qū)間的所有元素取出來(lái)，按照y排序。得到另外一個(gè)序列。
對(duì)于這個(gè)序列，我們有的信息是每一個(gè)元素的id ，而且這個(gè)序列是按照y有序的，所以通過(guò)y的從大到小的順序加入到樹(shù)狀數(shù)組中。加入的時(shí)候判斷一下ID。
如果id是在左邊，就更新，如果是在右邊就不用更新。為什么做邊就更新右邊不更新。因?yàn)槲覀冎荒艽_定右邊的id是比左邊大的，而同一邊的是不知道id的大小的關(guān)小的。
所以我們就用左邊去更新右邊的dp。
插入之后判斷有多少個(gè)在bit中的x比其小。
現(xiàn)在的問(wèn)題變成了嚴(yán)格遞增。
那么最后判斷的就是相等的問(wèn)題。
對(duì)于在bit中的x，我們可以直接詢問(wèn)的時(shí)候，詢問(wèn)1-z-1。這個(gè)容易想到。
對(duì)于y，我們?cè)诜种闻判虻臅r(shí)候，如果y相等，就把z大的放前面。
而對(duì)于x，我們就再開(kāi)一個(gè)bit，所有的放一起，和mid+1不相同的再放在一起。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <utility>
#define lowbit(x) (x&(-x))
#define maxn 300005
using namespace std;
struct node
{
int x,y,z,id;
bool operator < (const node &cmp)const
{
if(x!=cmp.x)return x<cmp.x;
if(y!=cmp.y)return y<cmp.y;
return z<cmp.z;
}
}p[maxn],b[maxn];
bool cmp_yz(node a,node b)
{
if(a.y!=b.y)return a.y<b.y;
return a.z>b.z;
}
int x[maxn];
int bit[2][maxn],dp[maxn];
int m;
void update(int &a,int b)
{
a=max(a,b);
}
void add(int index,int val,int g)
{
for(int idx=index;idx<=m;idx+=lowbit(idx))
update(bit[g][idx],val);
}
int query(int index,int g)
{
int res=0;
for(int idx=index;idx>=1;idx-=lowbit(idx))
{
update(res,bit[g][idx]);
}
return res;
}
void Clear(int index,int g)
{
for(int idx=index;idx<=m;idx+=lowbit(idx))
bit[g][idx]=0;
}
void solve(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);
int cnt=1;
for(int i=l;i<=r;i++)
{
b[cnt]=p[i];
b[cnt++].x=0;
}
int tx=p[mid+1].x;
sort(b+1,b+cnt,cmp_yz);
for(int i=1;i<cnt;i++)
{
if(b[i].id<=mid)
{
add(b[i].z,dp[b[i].id],0);
if(p[b[i].id].x!=tx)add(b[i].z,dp[b[i].id],1);
}
else
{
int t;
if(p[b[i].id].x!=tx)t=query(b[i].z-1,0);
else t=query(b[i].z-1,1);
t++;
update(dp[b[i].id],t);
}
}
for(int i=1;i<cnt;i++)
if(b[i].id<=mid)
{
Clear(b[i].z,0);
Clear(b[i].z,1);
}
solve(mid+1,r);
}
int ta , tb , C = ~(1<<31), M = (1<<16)-1;
int r() {
ta = 36969 * (ta & M) + (ta >> 16);
tb = 18000 * (tb & M) + (tb >> 16);
return (C & ((ta << 16) + tb)) % 1000000;
}
int main()
{
int n,tm;
while(scanf("%d%d%d%d",&n,&tm,&ta,&tb)!=EOF)
{
if(n+tm+ta+tb==0)break;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].z);
x[i]=p[i].z;
dp[i]=1;
bit[0][i]=bit[1][i]=0;
}
for(int i=n+1;i<=n+tm;i++)
{
p[i].x=r();
p[i].y=r();
p[i].z=r();
dp[i]=1;
bit[0][i]=bit[1][i]=0;
x[i]=p[i].z;
}
n+=tm;
sort(p+1,p+1+n);
sort(x+1,x+1+n);
m=unique(x+1,x+1+n)-x-1;
for(int i=1;i<=n;i++)
{
p[i].z=lower_bound(x+1,x+1+m,p[i].z)-x;
p[i].id=i;
}
solve(1,n);
int ans=0;
for(int i=1;i<=n;i++)
update(ans,dp[i]);
printf("%d
",ans);
}
return 0;
}
/*
6 0 1 1
0 0 0
0 2 2
1 1 1
2 0 2
2 2 0
2 2 2
5 0 1 1
0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
10 0 1 1
3 0 0
2 1 0
2 0 1
1 2 0
1 1 1
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3
0 10 1 1
5 0 0 0
1 1 1
2 1 2
3 1 3
4 1 4
5 1 5
0 0 0 0
*/
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
