【題解】TIOJ 1208 . 第K大連續和

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

int n, k, a[20005], bit[20005], ans;
vector <int> v;

int get_id(int x){
    return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
void update(int x){
    while (x <= v.size()){
        bit[x]++;
        x += x & (-x);
    }
}
int query(int x){
    int ret = 0;
    while (x){
        ret += bit[x];
        x -= x & (-x);
    }
    return ret;
}
bool check(int mid){
    memset(bit, 0, sizeof(bit));
    int ans = 0;
    for (int i = 0; i <= n; i++){
        ans += query(get_id(a[i]-mid+1)-1);
        update(get_id(a[i]));
    }
    return ans >= k;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    while (cin >> n >> k){
        if (n == 0) break;
        v.clear();
        ans = 0;
        v.push_back(0);
        for (int i = 1; i <= n; i++){
            cin >> a[i];
            a[i] += a[i-1];
            bit[i] = 0;
            v.push_back(a[i]);
        }
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        int l = -2e8, r = 2e8+1;
        while (r-l > 1){
            int mid = (l+r)/2;
            if (check(mid)) l = mid;
            else r = mid;
        }
        cout << l << "\n";
    }
}