nlogn[lis]
作者:
星和彦
,
2022-05-02 21:26:27
,
所有人可见
,
阅读 178
#include<bits/stdc++.h>
using namespace std;
int n , a[100010] , d[100010] , s[100010];
int main(){
cin >> n;
for(int i = 1 ; i <= n ; i ++ ) cin >> a[i];
memset( s , 0x3f , sizeof s );
s[0] = -1;
for(int i = 1 ; i <= n ; i ++ ){
int l = 0 , r = n;
while( l < r ){
int mid = (l + r + 1) >> 1;
if( s[mid] <= a[i] ) l = mid;
else r = mid - 1;
}
s[l + 1] = min( s[l + 1] , a[i]);
d[i] = l + 1;
}
for(int i = 1 ; i <= n ; i ++ ){
cout << i <<" " << d[i] << endl;
}
}