题目传送门

题意分析

记 \(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)\)。

//#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;
}