CFR 567 C. Geometric Progression ( Map )

Problem - 567C - Codeforces
題意：
給一個數列和 K，求有多少三個元素構成的有序遞增等比子序列，其比為 K。
解法：
預處理，使可以查詢每個值存在於哪些位置，且這些位置是排序好的。接著枚舉中間的數字，左右邊的數字將會隨之確定，因此將答案增加指定數字在右方的數量*指定數字在左方的數量。數數量的方法就是用 lower_bound 那一類，以枚舉的數字的位置為 value 去搞。

int N, K;
vi A;

void init(){
    cin >> N >> K;
    A = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];
}

map< int, vi > v2p;

void preprocess(){
    for( int i = 0; i < N; ++i )
        v2p[ A[ i ] ].push_back( i );
}

void solve(){
    ll ans = 0;
    for( int i = 1; i + 1 < N; ++i ){
        int lv = A[ i ] / K;
        if( abs( lv ) > ( int ) 1e9 or lv * K != A[ i ] )
            continue;
        ll rv = A[ i ] * K;
        if( abs( rv ) > ( int ) 1e9 or rv / K != A[ i ] )
            continue;
        int lcnt = lower_bound( v2p[ lv ].begin(), v2p[ lv ].end(), i ) - v2p[ lv ].begin();
        int rcnt = v2p[ rv ].end() - upper_bound( v2p[ rv ].begin(), v2p[ rv ].end(), i );
        ans += 1LL * lcnt * rcnt;
    }
    cout << ans << endl;
}