题意:
序列arr[i--n];输出以a[i]为结尾的最长上升子序列。1<=n<=100000;
思路:
O(n*log(n)),求最长上升子序列。
#include#include #include #include using namespace std;const int maxn = 100000+100;int arr[maxn];int main (){ int T;scanf("%d",&T); while(T--) { int n,k=0;scanf("%d",&n); for(int i=1;i<=n;i++) { int t; scanf("%d",&t); int pos=int(lower_bound(arr,arr+k,t)-arr); printf("%d",pos+1); if(i