Segment tree - Number of free elements in each segments
Intuition\n Describe your first thoughts on how to solve this problem. \nIn each segment store number of free servers, then for a arrival just query from the i%
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIn each segment store number of free servers, then for a arrival just query from the i%k -> k - 1 segment to find out the first segment still have cnt (cnt != 0), otherwise query the first segment have cnt != 0 from 0 -> i%k - 1.\n\n# Code\n```cpp []\n#define ll long long\nclass Solution {\npublic:\n    vector<int> segtree;\n    void build(int idx, int s, int e) {\n        if (s == e) {\n            segtree[idx] = 1;\n            return;\n        }\n        int m = (s + e)/2;\n        build(2*idx, s, m);\n        build(2*idx + 1, m + 1, e);\n        segtree[idx] = segtree[2*idx] + segtree[2*idx + 1];\n    }\n    void update(int idx, int s, int e, int pos, int val) {\n        if (s == e) {\n            segtree[idx] = val;\n            return;\n        }\n        int m = (s + e)/2;\n        if (pos <= m) update(2*idx, s, m, pos, val);\n        else update(2*idx + 1, m + 1, e, pos, val);\n        segtree[idx] = segtree[2*idx] + segtree[2*idx + 1];\n    }\n    int query(int idx, int s, int e, int l, int r) {\n        if (s > r || e < l) return -1;\n        if (segtree[idx] == 0) return -1;\n        if (s == e) return s;\n        int m = (s + e)/2;\n        int res1 = query(2*idx, s, m, l, r);\n        if (res1 != -1) return res1;\n        int res2 = query(2*idx + 1, m + 1, e, l, r);\n        return res2;\n    }\n    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {\n        segtree.resize(4*k);\n        build(1, 0, k - 1);\n        priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;\n        int used = 0;\n        vector<int> cnt(k);\n        int mx = -1;\n        for (int i = 0; i < arrival.size(); i++) {\n            while (pq.size() && pq.top().first <= arrival[i]) {\n                auto p = pq.top(); pq.pop();\n                update(1, 0, k - 1, p.second, 1);\n                used--;\n            }\n            if (used == k) {\n                continue;\n            }\n\n            int idx = i%k;\n            used++;\n            int x = query(1, 0, k - 1, idx, k - 1);\n            if (x == -1) x = query(1, 0, k - 1, 0, idx - 1);\n            update(1, 0, k - 1, x, 0);\n            cnt[x]++;\n            mx = max(mx, cnt[x]);\n            pq.push({arrival[i] + load[i], x});\n        }\n        vector<int> res;\n        for (int i = 0; i < k; i++) if (cnt[i] == mx) res.push_back(i);\n        return res;\n    }\n};\n```
['C++']