洛谷1314 聪明的质监员

题意

有 $N$ 个矿石，价值和重量为 $V_i,W_i$ 。需要选择一个值 $W$ ，对于区间 $[l,r]$ ，校验值为

$$\sum_j 1 \times \sum_j V_j \ \ (j\in [l,r] \ , \ W_j > W) $$

总校验值为 $M$ 个区间校验值的总和。求最小总校验值。

$N,M\le 200000$ 。

题解

我纠结了半天 $\sum_j 1$ 到底是啥，直到去看了讨论才知道（捂脸），就是满足条件的 $j$ 的个数。

显然 $W$ 越小，校验值越大，反之亦然。所以可以二分，然后对 $V_j$ 的和以及满足条件的个数分别做前缀和即可。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

ll n,m,ans=1e18,S,v[200005],w[200005],L[200005],R[200005],sum[200005],cnt[200005];

inline bool check(ll mid)
{
    for (ll i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+(w[i]>=mid)*v[i];
        cnt[i]=cnt[i-1]+(w[i]>=mid);
    }
    ll res=0;
    for (ll i=1;i<=m;i++) res+=(sum[R[i]]-sum[L[i]-1])*(cnt[R[i]]-cnt[L[i]-1]);
    ans=min(ans,abs(res-S));
    if (res<S) return 1;
    return 0;
}

signed main()
{
    n=read(); m=read(); S=read();
    ll mx=0;
    for (ll i=1;i<=n;i++) w[i]=read(),v[i]=read(),mx=max(mx,w[i]);
    for (ll i=1;i<=m;i++) L[i]=read(),R[i]=read();
    ll l=0,r=mx+1;
    while (l<r)
    {
        ll mid=(l+r)>>1;
        if (check(mid)) r=mid;
        else l=mid+1;
    }
    return !printf("%lld",ans);
}