【CSES】1143. Hotel Queries

題目連結

時間複雜度

• $O(MlogN)$

解題想法

題目希望你做到的事情：

給定一個陣列，找出 ind 最小且值大於等於 k 的資料，找到後回傳 ind
如果值不存在則回傳 0

這題的想法就是在線段樹上面進行二分搜

大概的想法就是每當抵達一個節點時就檢查他的左右子節點值的大小，如果大於等於的話就往下走，直到走到葉節點

當走到葉節點時，將值減去 k，並回傳 L 或 R（會剛好是 ind）

完整程式

實作需要注意的事情：

1. 如果要將 ans 開在全域要記得每次走之前都要更新值
2. 要在一輸入的時候就先判斷樹上是否有至少一個點可以輸出
   • 這個可以透過比較輸入的值跟 seg[0] 的大小來取得（從定義可以知道 seg[0] 存的資料一定為整個樹最大的值）
3. 可以查詢跟修改同時做，這樣複雜度比較漂亮
4. 記得修改完值之後要往上更新資料，不然會出事

/* Question : CSES 1143. Hotel Queries */

#include<bits/stdc++.h>
using namespace std;

#define opt ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pirq(type) priority_queue<type, vector<type>, greater<type>>
#define mem(x, value) memset(x, value, sizeof(x));
#define pii pair<int, int>
#define pdd pair<double, double>
#define pb push_back
#define f first
#define s second
#define int long long

#define nL cnt * 2
#define nR cnt * 2 + 1

const auto dir = vector< pair<int, int> > { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
const int MAXN = 2e5 + 50;
const int Mod = 1e9 + 7;
int n, m, p, ans, hotel[MAXN], seg[MAXN*4];

int findk( int L, int R, int val, int cnt ){
    if( L == R ){
        seg[cnt] -= val;
        return L;
    }

    int M = (L + R) / 2;
    if( seg[nL] >= val ) ans = findk(L, M, val, nL);
    else if( seg[nR] >= val ) ans = findk(M+1, R, val, nR);

    seg[cnt] = max( seg[nL], seg[nR] );
    return ans;
}

void build( int L, int R, int cnt ){
    if( L == R ){
        seg[cnt] = hotel[L];
        return;
    }

    int M = (L + R) / 2;
    build(L, M, nL);
    build(M+1, R, nR);
    seg[cnt] = max( seg[nL], seg[nR] );
}

signed main(){
    opt;
    cin >> n >> m;
    for( int i = 1 ; i <= n ; i++ ) cin >> hotel[i];
    build(1, n, 1);

    for( int i = 0 ; i < m ; i++ ){
        cin >> p;
        ans = 0;
        if( seg[1] < p ) cout << 0 << " \n"[i==m-1];
        else cout << findk(1, n, p, 1) << " \n"[i==m-1];
    }
}