UvaLive 6667 Longest Chain (分治求三维LIS)
来源：程序员人生 发布时间：2014-10-03 08:00:01 阅读次数：2743次
题目大意：
题目给出了定义的小于号，然后求出一个LIS。。。
思路分析：
这道题目的是一个严格递增的，和 Hdu 4742 类似。只不过Hdu的这道题是一个不递减的序列。
简单说一下Hdu 4742的做法。
首先我们可以想到的是一维的LIS，那么简单就是n。
然后二维的LIS，就是先排序一维，然后用求第二维的LIS。
现在问题扩展到三维。依然排序一维。
假设我们排序的是z。
然后记下排序后的id。现在已知，id小的z就小。
然后开始分治，类似线段树的递归。对于一个区间，我们将这个区间的所有元素取出来，按照y排序。得到另外一个序列。
对于这个序列，我们有的信息是每一个元素的id ，而且这个序列是按照y有序的，所以通过y的从大到小的顺序加入到树状数组中。加入的时候判断一下ID。
如果id是在左边，就更新，如果是在右边就不用更新。为什么做边就更新右边不更新。因为我们只能确定右边的id是比左边大的，而同一边的是不知道id的大小的关小的。
所以我们就用左边去更新右边的dp。
插入之后判断有多少个在bit中的x比其小。
现在的问题变成了严格递增。
那么最后判断的就是相等的问题。
对于在bit中的x，我们可以直接询问的时候，询问1-z-1。这个容易想到。
对于y，我们在分治排序的时候，如果y相等，就把z大的放前面。
而对于x，我们就再开一个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
*/
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
