bzoj3173【TJOI2013】最长上升子序列
程序员文章站
2022-08-31 18:47:01
Description
给定一个序列,初始为空。现在我们将1到N的数字插入到序列中,每次将一个数字插入到一个特定的位置。每插入一个数字,我们都想知道此时最长上升子序列长度是多少?...
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
30 0 2
Sample Output
11
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
下一篇: Linux: yum 命令说明