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
",mx);
72         for(int i=st,cnt=0;i<=n;i=pre[i])printf("%d%c",i," 
"[++cnt==mx]);
73     }
74     return 0;
75 }

View Code