hdu 1025 n*logn最长上升子序列

 1 /*
 2 TLE
 3 */
 4 #include <iostream>
 5 #include <cstdio>
 6 #include <cstring>
 7 using namespace std;
 8 
 9 const int maxn=5e5+5;
10 int a[maxn],b[maxn],c[maxn],f[maxn<<1];
11 inline int max(int a,int b){return a>b?a:b;}
12 void swap(int &a,int &b){int t=a;a=b;b=t;}
13 void qsort(int l,int r)
14 {
15     if(l<r)
16     {
17         int key=b[l],i=l,j=r;
18         while(i!=j)
19         {
20             while(b[j]>=key && i<j) j--;
21             while(b[i]<=key && i<j) i++;
22             if(i<j) swap(b[i],b[j]);
23         }
24         b[l]=b[i];b[i]=key;
25         qsort(l,i-1);
26         qsort(i+1,r);
27     }
28 }
29 int binary_search(int l,int r,int val)
30 {
31     int mid;
32     while(l<=r)
33     {
34         mid=(l+r)>>1;
35         if(c[mid]>val) r=mid-1;
36         else if(c[mid]==val) return mid;
37         else l=mid+1;
38     }
39     return -1;
40 }
41 void updata(int pos,int v,int l,int r,int rt)
42 {
43     if(l==r)
44     {
45         f[rt]=v;return;
46     }
47     int mid=(l+r)>>1;
48     if(pos<=mid) updata(pos,v,l,mid,rt<<1);
49     else updata(pos,v,mid+1,r,rt<<1|1);
50 }
51 int query(int L,int R,int l,int r,int rt)
52 {
53     if(L<=l && r<=R)
54         return f[rt];
55     int mid=(l+r)>>1;
56     int ans;
57     if(L<=mid) ans=query(L,R,l,mid,rt<<1);
58     if(R>mid) ans=max(ans,query(L,R,mid+1,r,rt<<1|1));
59     return ans;
60 }
61 int main()
62 {
63     int icase=0,n,tmp,i,cnt;
64     while(~scanf("%d",&n))
65     {
66         for(i=1;i<=n;i++) 
67         {
68             scanf("%d%d",&tmp,a+i);b[i]=a[i];
69         }
70         qsort(1,n);cnt=1;c[1]=b[1];
71         for(i=2;i<=n;i++)
72             if(b[i]!=b[i-1])
73                 c[++cnt]=b[i];
74         memset(f,0,sizeof(f));
75         int ans=0,maxv,x;
76         for(i=1;i<=n;i++)
77         {
78             x=binary_search(1,cnt,a[i]);
79             if(x>1) maxv=query(1,x-1,1,cnt,1);
80             else maxv=0;
81             updata(x,maxv+1,1,cnt,1);
82             if(maxv+1>ans) ans=maxv+1;
83         }
84         printf("Case %d:
",++icase);
85         if(ans==1) printf("My king, at most 1 road can be built.

");
86         else printf("My king, at most %d roads can be built.

",ans);
87     }
88     return 0;
89 }
90 /*
91 2
92 1 2
93 2 1
94 3
95 1 2
96 2 3
97 3 1
98 */

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn=5e+5;
 7 int dp[maxn],f[maxn];
 8 
 9 int upper_bound(int l,int r,int val)//二分求上界
10 {
11     int mid,ans=-1;
12     while(l<=r)
13     {
14         mid=(l+r)>>1;
15         if(dp[mid]>=val) ans=mid,r=mid-1;
16         else l=mid+1;
17     }
18     return ans;
19 }
20 
21 int main()
22 {
23     int icase=0,n,i,cnt,x,y;
24     while(~scanf("%d",&n))
25     {
26         for(i=1;i<=n;i++)
27         {
28             scanf("%d%d",&x,&y);
29             f[x]=y;
30         }
31         dp[1]=f[1];cnt=1;
32         for(i=1;i<=n;i++)
33         {
34             x=upper_bound(1,cnt,f[i]);
35             if(x==-1) dp[++cnt]=f[i];
36             else dp[x]=f[i];
37         }
38         printf("Case %d:
",++icase);
39         if(cnt==1) printf("My king, at most 1 road can be built.

");
40         else printf("My king, at most %d roads can be built.

",cnt);
41     }
42     return 0;
43 }