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 + ;

const int Maxn = 1e6 + ;

const ll inf = 1LL << ;

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 = ; char ch = ; T op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline ll solve(int mid) {

    sumCnt[] = , sumVal[] = 0LL;

    for(int i = ; i <= n; i++) {

        sumCnt[i] = sumCnt[i - ], sumVal[i] = sumVal[i - ];

        if(w[i] >= mid) ++sumCnt[i], sumVal[i] += v[i];

    }

    ll res = 0LL;

    for(int i = ; i <= m; i++)

        res += 1LL * (sumCnt[seg[i].r] - sumCnt[seg[i].l - ]) * (sumVal[seg[i].r] - sumVal[seg[i].l - ]);

    return res;

}

int main() {

    read(n), read(m), read(cur);

    for(int i = ; i <= n; i++)

        read(w[i]), read(v[i]);

    for(int i = ; i <= m; i++)

        read(seg[i].l), read(seg[i].r);

    int ln = , rn = Maxn, mid, res = ;

    for(; ln <= rn; ) {

        mid = (ln + rn) / ;

        if(solve(mid) <= cur) rn = mid - , res = mid;

        else ln = mid + ;

    }

    ll tmp = solve(res), ans = cur - tmp;

    ln = , rn = Maxn, res = Maxn;

    for(; ln <= rn; ) {

        mid = (ln + rn) / ;

        if(solve(mid) >= cur) ln = mid + , res = mid;

        else rn = mid - ;

    }

    tmp = solve(res);

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

    printf("%lld\n", ans);

    return ;

}

巴特西

Luogu 1314 [NOIP2011] 聪明的质监员

最新文章

热门文章