本文主要是介绍2019HDU多校第六场——HDU6635 Nonsense Time【树状数组求LIS】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目链接: HDU6635 Nonsense Time
Time Limit: 14000/14000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Problem Description
You a given a permutation p1,p2,…,pn of size n. Initially, all elements in p are frozen. There will be n stages that these elements will become available one by one. On stage i, the element pki will become available.
For each i, find the longest increasing subsequence among available elements after the first i stages.Input
The first line of the input contains an integer T(1≤T≤3), denoting the number of test cases.
In each test case, there is one integer n(1≤n≤50000) in the first line, denoting the size of permutation.
In the second line, there are n distinct integers p1,p2,...,pn(1≤pi≤n), denoting the permutation.
In the third line, there are n distinct integers k1,k2,...,kn(1≤ki≤n), describing each stage.
It is guaranteed that p1,p2,...,pn and k1,k2,...,kn are generated randomly.Output
For each test case, print a single line containing n integers, where the i-th integer denotes the length of the longest increasing subsequence among available elements after the first i stages.
Sample Input
1
5
2 5 3 1 4
1 4 5 3 2
Sample Output
1 1 2 3 3
题意:
给你一个1~n的排列a和排列b,起始状态a中所有数都是冻结的,i时刻a中b[i]这个数解冻,计算出当前a中已解冻的数的最长上升子序列。
分析:
正难则反,考虑倒着处理,按照b倒序冻结a中的数;
第n个时刻所有数都已解冻,树状数组求出当前的LIS并标记当前构成LIS,然后向前更新,如果当前冻结的数不在LIS中,那么不改变,否则再次求解LIS;
可以证明,这样的时间复杂度是。
Tips:类似链表的方式记录前后指针,给原序列加上前后端点,这样就可以快速的得到冻结某个数之后的序列。
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e4+7;
int a[maxn],b[maxn],vis[maxn],tag[maxn];
int LIS[maxn],bit[maxn],pre[maxn],nxt[maxn],ans[maxn];
int n;
int lowbit(int x) {return x&-x;}
void getLIS()
{for (int i=nxt[0];i<=n+1;i=nxt[i]){vis[i]=0;int tmp=0,res=a[i];while (res){if(LIS[tmp]<LIS[bit[res]]) tmp=bit[res];res-=lowbit(res);}LIS[i]=LIS[tmp]+1;tag[i]=tmp;res=a[i];while (res<=n+2){if(LIS[bit[res]]<LIS[i]) bit[res]=i;res+=lowbit(res);}}for (int i=nxt[0];i<=n+1;i=nxt[i]){int res=a[i];while (res<=n+2){bit[res]=0;res+=lowbit(res);}}for (int i=n+1;i;i=tag[i]) vis[i]=1;
}
void rua()
{scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]++;a[0]=1;a[n+1]=n+2;for (int i=0;i<=n+1;i++) {pre[i]=i-1;nxt[i]=i+1;vis[i]=bit[i]=0;}bit[n+2]=0;for (int i=1;i<=n;i++) scanf("%d",&b[i]);getLIS();for (int i=n;i;i--){ans[i]=LIS[n+1]-1;int x=b[i];pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];if(vis[x]) getLIS();}for (int i=1;i<n;i++) printf("%d ",ans[i]);printf("%d\n",ans[n]);
}
int main()
{int t;scanf("%d",&t);while (t--) rua();return 0;
}
这篇关于2019HDU多校第六场——HDU6635 Nonsense Time【树状数组求LIS】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!