Luogu 1314 [NOIP2011] 聪明的质监员

二分答案 + 前缀和。

题面中式子的意思是每一个区间$[l, r]$的贡献是这个区间内$w_i geq W$的个数乘以这些$i$的$v_i$和。

很快发现了答案具有单调性，可以做两遍二分，分别看看小于$S$的值最大能取到多少以及大于$S$的最小能取到多少，然后取个$min$。

思考一下怎么判定，查询一个区间内比一个数大的数的个数和权值和，莫不是主席树？？？

被$dalao$$D$了，只要每一次都算一遍前缀和就好了，如果$w_i geq W$就把$i$和$v_i$计入贡献，查询是$O(1)$的。

时间复杂度$O(nlogn)$。

如果是主席树还多一个$log$。

Code：

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
const int Maxn = 1e6 + 5;
const ll inf = 1LL << 60;

int n, m, w[N], sumCnt[N];
ll cur, v[N], sumVal[N];

struct Segment {
    int l, r;
} seg[N];

template <typename T>
inline void read(T &X) {
    X = 0; char ch = 0; T op = 1;
    for(; ch > '9' || ch < '0'; ch = getchar())
        if(ch == '-') op = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar())
        X = (X << 3) + (X << 1) + ch - 48;
    X *= op;
}

inline ll solve(int mid) {
    sumCnt[0] = 0, sumVal[0] = 0LL;
    for(int i = 1; i <= n; i++) {
        sumCnt[i] = sumCnt[i - 1], sumVal[i] = sumVal[i - 1];
        if(w[i] >= mid) ++sumCnt[i], sumVal[i] += v[i];
    }

    ll res = 0LL;
    for(int i = 1; i <= m; i++) 
        res += 1LL * (sumCnt[seg[i].r] - sumCnt[seg[i].l - 1]) * (sumVal[seg[i].r] - sumVal[seg[i].l - 1]);
    
    return res;
}

int main() {
    read(n), read(m), read(cur);
    for(int i = 1; i <= n; i++) 
        read(w[i]), read(v[i]);
    for(int i = 1; i <= m; i++)
        read(seg[i].l), read(seg[i].r);
    
    int ln = 0, rn = Maxn, mid, res = 0;
    for(; ln <= rn; ) {
        mid = (ln + rn) / 2;
        if(solve(mid) <= cur) rn = mid - 1, res = mid;
        else ln = mid + 1;
    }

    ll tmp = solve(res), ans = cur - tmp;
    ln = 0, rn = Maxn, res = Maxn;
    for(; ln <= rn; ) {
        mid = (ln + rn) / 2;
        if(solve(mid) >= cur) ln = mid + 1, res = mid;
        else rn = mid - 1;
    }

    tmp = solve(res);
    if(tmp - cur < ans) ans = tmp - cur;

    printf("%lld
", ans);
    return 0;
}