题意分析
记 $W=x$ 时，答案为 $\textit{calc}(x)$。
则可以发现，答案为：
\[\textit{calc}(W)=\sum_{i=1}^my_i=\sum_{i=1}^m\left(\sum_{j=l_i}^{r_i}[w_j\geq W]\times\sum_{j=l_i}^{r_i}[w_j\geq W]v_j\right)\]显然，当 $W$ 越大时，满足 $w_j\geq W$ 的 $j$ 就越少，则 $\textit{calc}(W)$ 就越大。
因此，可以考虑二分答案。
为了让检验结果尽可能接近 $s$，可以二分一个 $W$，使得 $W$ 满足 $\textit{calc}(W)\geq s$ 且不存在 $W’<W\land calc(W’)\geq s$，即 $\textit{calc}(W)>s,\textit{calc}(W-1)<s$。
那么现在的问题就是如何写出一个较为高效的二分答案的 check。
记当前二分出来的 $W$ 为 $\textit{mid}$，check 即计算 $\textit{calc}(\textit{mid})$，判断 $\textit{calc}(\textit{mid})\geq s$ 是否成立。
外层 $\mathcal O(m)$ 求和不好优化，考虑优化内层求和。
注意到 $l_i,r_i$ 显然是一段区间，因此可以考虑做前缀和，然后差分还原。
记：
\[\textit{preW}_i=\sum_{j=1}^i[w_j>W]\\ \textit{preV}_i=\sum_{j=1}^i[w_j>W]v_j\\\]$\textit{preW},\textit{preV}$ 显然都是可以 $\mathcal O(n)$ 预处理出来的，求和时单次 $\mathcal O(1)$ 即可。
check 的总时间复杂度为 $\mathcal O(n+m)=\mathcal O(n)$。
优化技巧
显然，影响 $[w_j\geq W]$ 的只有 $W$ 与每一个 $w_j$ 的关系。
那么令 $W=w_k$，则若不存在 $k’$，使得 $W-1=w_{k’}$，则 $\textit{calc}(W)=\textit{calc}(W-1)$。
因此可以将原来的在值域 $[0,s]$ 上二分改为在 $w$ 上二分。
当然，为了使 $w$ 单调，显然需要排序。
这样，时间复杂度便从 $\mathcal O(n\log V)$ 降到了 $\mathcal O(n\log n)$。
AC 代码
时间复杂度：$\mathcal O(n\log n)$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<random>
using namespace std;
typedef long long ll;
typedef __int128 lll;
constexpr const int N=2e5,M=N;
constexpr const ll S=1e12;
constexpr const lll Ans=(lll)N*N*N*1e6;
mt19937 Rand(time(0));
struct stone{
int w,v;
}a[N+1];
struct query{
int l,r;
}q[M+1];
int n,m;
ll s;
lll calc(int w){
lll ans=0;
static int preW[N+1];
static ll preV[N+1];
for(int i=1;i<=n;i++){
preW[i]=preW[i-1]+(a[i].w>=w);
}
for(int i=1;i<=n;i++){
preV[i]=preV[i-1]+(a[i].w>=w)*a[i].v;
}
for(int i=1;i<=m;i++){
ans+=(lll)(preW[q[i].r]-preW[q[i].l-1])*(preV[q[i].r]-preV[q[i].l-1]);
}
return ans;
}
template<typename T>
T abs(T x){
if(x<0){
return -x;
}
return x;
}
template<typename T>
void Write(T x){
static char s[101];
int top=0;
do{
s[++top]=x%10+'0';
x/=10;
}while(x);
while(top){
cout<<s[top--];
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
cin>>a[i].w>>a[i].v;
}
for(int i=1;i<=m;i++){
cin>>q[i].l>>q[i].r;
}
lll ans=Ans+1;
static int w[N+1];
for(int i=1;i<=n;i++){
w[i]=a[i].w;
}
sort(w+1,w+n+1);
int l=1,r=n;
while(l<=r){
int mid=l+r>>1;
lll pl=calc(w[mid]);
ans=min(ans,abs(pl-s));
if(pl-s>0){
l=mid+1;
}else{
r=mid-1;
}
}
Write(ans);
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
