程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj3173【TJOI2013】最長上升子序列

bzoj3173【TJOI2013】最長上升子序列

編輯:C++入門知識

bzoj3173【TJOI2013】最長上升子序列


Description

給定一個序列,初始為空。現在我們將1到N的數字插入到序列中,每次將一個數字插入到一個特定的位置。每插入一個數字,我們都想知道此時最長上升子序列長度是多少?

Input

第一行一個整數N,表示我們要將1到N插入序列中,接下是N個數字,第k個數字Xk,表示我們將k插入到位置Xk(0<=Xk<=k-1,1<=k<=N) 

Output

N行,第i行表示i插入Xi位置後序列的最長上升子序列的長度是多少。

Sample Input

3
0 0 2

Sample Output

1
1
2  

HINT

100%的數據 n<=100000

二分+樹狀數組求出每個數最後的位置。每次插入後的LIS等於1-pos的LIS+1,用樹狀數組維護前綴的最大值。

#include
#include
#include
#include
#include
#include
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 100005
using namespace std;
int n,ans;
int a[maxn],s[maxn];
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline int query(int x)
{
	int ret=0;
	for(;x;x-=x&(-x)) ret+=s[x];
	return ret;
}
inline void change(int x)
{
	for(;x<=n;x+=x&(-x)) s[x]++;
}
inline int query2(int x)
{
	int ret=0;
	for(;x;x-=x&(-x)) ret=max(ret,s[x]);
	return ret;
}
inline void change2(int x,int y)
{
	for(;x<=n;x+=x&(-x)) s[x]=max(s[x],y);
}
int main()
{
	n=read();
	F(i,1,n) a[i]=read()+1;
	D(i,n,1)
	{
		int l=1,r=n,mid,tmp;
		while (l>1;
			tmp=mid-query(mid);
			if (tmp

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved