# Luogu-P4755 Beautiful Pair

Title meaning

Small D has a sequence ${a}$, when a number pair $(i,j)$ ($i \le j$) satisfies the product of $a_i$ and $a_j$ is not greater than $a_i, a_{i+1 }, \ldots, a_j$, Little D thinks this pair is beautiful. Please find the number of beautiful pairs.

$1\le n\le{10}^5$, $1\le a_i\le{10}^9$.

problems while programming

• Not familiar with ST tables!
• What’s more, there is a problem with the understanding of lower_bound and upper_bound . Let’s review the elementary school knowledge: lower_bound is to find the position of “greater than or equal to”, upper_bound is “greater than”. When I was writing this question, I used lower_bound inexplicably to find a position less than a certain number, and there was no -1 .

In summary, I am zz.

train of thought

Consider divide and conquer (it is said that this is a routine), we find the maximum position $mid$ in an interval $[l, r]$, then count all the answers across $mid$, and then recursively process $[l, mid -1], [mid+1, r]$. Suppose the number on the left of $mid$ is $a_i$, and the number on the right is $a_j$. According to the title, $a_i * a_j \le a_{mid}$, that is, $a_j \le \lfloor\frac{a_{mid}} {a_i}\rfloor$. Then we enumerate $a_i$, and then use the chairman tree to count the number of numbers less than $\lfloor\frac{a_{mid}}{a_i}\rfloor$ in the right interval.

Note that the smaller length of the left and right intervals needs to be enumerated each time, so that $O(n\log^2n)$ can be achieved. Otherwise it will be stuck as $O(n^2\log n)$.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84   #include using namespace std ; const int N = 100005 , LOGN = 18 ; int n , a [ N ], b [ N ], bn , f [ N ][ LOGN ], logn [ N ], root [ N ], cnt ; struct node { int sum , ls , rs ; } t [ N * 25 ]; void update ( int & rt , int pre , int pos , int l , int r ) { rt = ++ cnt ; t [ rt ] = t [ pre ]; t [ rt ]. sum ++ ; if ( l == r ) return ; int mid = ( l + r ) >> 1 ; if ( pos <= mid ) update ( t [ rt ]. ls , t [ pre ]. ls , pos , l , mid ); else update ( t [ rt ]. rs , t [ pre ]. rs , pos , mid + 1 , r ); } int query ( int rt , int pre , int x , int y , int l , int r ) { if ( l >= x && r <= y ) return t [ rt ]. sum - t [ pre ]. sum ; int mid = ( l + r ) >> 1 ; int ret = 0 ; if ( x <= mid ) ret += query ( t [ rt ]. ls , t [ pre ]. ls , x , y , l , mid ); if ( y > mid ) ret += query ( t [ rt ]. rs , t [ pre ]. rs , x , y , mid + 1 , r ); return ret ; } void buildst () { logn [ 1 ] = 0 ; logn [ 2 ] = 1 ; for ( int i = 3 ; i < N ; i ++ ) logn [ i ] = logn [ i / 2 ] + 1 ; for ( int i = 1 ; i <= n ; i ++ ) f [ i ][ 0 ] = i ; for ( int t = 1 ; t < LOGN ; t ++ ) { for ( int i = 1 ; i + ( 1 << t ) - 1 <= n ; i ++ ) { if ( a [ f [ i ][ t - 1 ]] > a [ f [ i + ( 1 << ( t - 1 ))][ t - 1 ]]) f [ i ][ t ] = f [ i ][ t - 1 ]; else f [ i ][ t ] = f [ i + ( 1 << ( t - 1 ))][ t - 1 ]; } } } int getmax ( int l , int r ) { int t = logn [ r - l + 1 ]; // NOT f[l+(1<<(t-1))-1][t] if ( a [ f [ l ][ t ]] > a [ f [ r - ( 1 << t ) + 1 ][ t ]]) return f [ l ][ t ]; return f [ r - ( 1 << t ) + 1 ][ t ]; } long long ans = 0 ; void solve ( int l , int r ) { if ( l > r ) return ; if ( l == r ) { ans += ( a [ l ] == 1 ); return ; } int mid = getmax ( l , r ); if ( mid - l + 1 <= r - mid + 1 ) { // 枚举左半区间for ( int i = l ; i <= mid ; i ++ ) { // 不能用lowerbound int idx = upper_bound ( b + 1 , b + 1 + bn , a [ mid ] / a [ i ]) - b - 1 ; if ( idx != 0 ) ans += query ( root [ r ], root [ mid - 1 ], 1 , idx , 1 , bn ); } } else { // 枚举右半区间for ( int i = mid ; i <= r ; i ++ ) { int idx = upper_bound ( b + 1 , b + 1 + bn , a [ mid ] / a [ i ]) - b - 1 ; if ( idx != 0 ) ans += query ( root [ mid ], root [ l - 1 ], 1 , idx , 1 , bn ); } } solve ( l , mid - 1 ); solve ( mid + 1 , r ); } int main () { ios :: sync_with_stdio ( false ); cin >> n ; for ( int i = 1 ; i <= n ; i ++ ) cin >> a [ i ], b [ i ] = a [ i ]; sort ( b + 1 , b + 1 + n ); bn = unique ( b + 1 , b + 1 + n ) - b - 1 ; root [ 0 ] = ++ cnt ; buildst (); for ( int i = 1 ; i <= n ; i ++ ) { int id = lower_bound ( b + 1 , b + 1 + bn , a [ i ]) - b ; update ( root [ i ], root [ i - 1 ], id , 1 , bn ); } solve ( 1 , n ); cout << ans << endl ; return 0 ; }