让结果最接近\(s\)值，显然我们要二分\(w\),check的写法可以直接暴力模拟，如果check(mid)<s则将r右移（通过读公式可以知道\(w\)越小检验值\(y\)就越大）
但是这样会TLE，再读一下柿子：
\(y_i=\sum\limits_{j=l_i}^{r_i}[w_j \ge W] \times \sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j\)
显然可以前缀和优化，每次check前分别前缀和记录一下\(sum1=\sum\limits_{j=l_i}^{r_i}[w_j \ge W]\)和$ sum2=\sum\limits_{j=l_i}^{r_i}[w_j \ge W]v_j$。
这样check过程中可以直接求 \(sum1,sum2\)，\(sum1\times sum2\)就是检验值\(y_i\)，另设一个变量ans+=sum1*sum2即可
通过这样的优化，对检验值\(y_i\)的计算我们每次check只需要计算一次（每次check \(w\)是唯一的，即\(y_i\)是唯一的）大大提高了效率
代码实现
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define N 1000000
#define ll long long
#define INF 0x3f3f3f3f3f
using namespace std;
ll n,m,s;
ll ans = INF;
ll l[N],r[N],w[N],v[N];
ll l_sum1[N],l_sum2[N];
void update(ll lll,ll rr,ll d,ll d1)
{
l_sum1[lll] ++;
l_sum1[rr+1] --;
l_sum2[lll] += d;
l_sum2[rr+1] -= d;
}
bool check(ll x)
{
memset(l_sum1,0,sizeof(l_sum1));
memset(l_sum2,0,sizeof(l_sum2));
ll check_num = 0;
for(int i=1;i<=n;i++)
{
if(w[i] >= x)
{
l_sum1[i] = l_sum1[i-1]+1;
l_sum2[i] = l_sum2[i-1]+v[i];
}
else
{
l_sum1[i] = l_sum1[i-1];
l_sum2[i] = l_sum2[i-1];
}
}
for(ll i = 1;i <= m;i ++)
{
ll c1 = 0,c2 = 0;
c1 = l_sum1[r[i]] - l_sum1[l[i]-1];
c2 = l_sum2[r[i]] - l_sum2[l[i]-1];
check_num += c1*c2;
}
if(abs(check_num-s) < ans) ans = abs(check_num-s);
return check_num >= s;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&s);
for(ll i=1;i<=n;i++)
{
scanf("%lld%lld",&w[i],&v[i]);
}
for(ll i =1;i<=m;i++) scanf("%lld%lld",&l[i],&r[i]);
ll l = INF,r = 0;
for(ll i =1;i<=n;i++)
{
l = min(l,w[i]);
r = max(r,w[i]);
}
while(l <= r)
{
ll mid = (l+r+1)/2;
if(check(mid) ) l = mid+1;
else r = mid -1;
}
cout<<ans<<endl;
// cout<<min(abs(check(ans+1) - s),abs(check(ans) - s))<<endl;
return 0;
}