NOIp2011 聪明的质监员 二分+前缀和

因为每个W被有效利用一次，共logmaxm次，又每次都要查很多可能有重叠的区间，所以可以每次求前缀和，从而加速每次查询。

一开始并没有想到用前缀和，因为没有注意到每次查询有大量重复计算及本题可用两个前缀和处理的性质。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;

ll read(){
    ll a = 0;char l = ' ',c = getchar();
    while(c < '0'||c > '9')l = c,c = getchar();
    while('0' <= c&&c <= '9')a = a*10+c-'0',c = getchar();
    if(l == '-')return -a; return a;
}

const ll Maxn = 1e6+10;
ll l[Maxn],r[Maxn],v[Maxn],w[Maxn],s1[Maxn],s2[Maxn];
ll n,m,s,ans,ansv = 1e13,miv = 1e13,mav = -1e13;

ll mywork(ll wi){
    ll cur,cnt,tot = 0;
    for(ll i = 1;i <= m;i++){
        cur = cnt = 0;
        for(ll j = l[i];j <= r[i];j++)if(w[j] >= wi)
            cur += v[j],cnt++;

        tot += cur*cnt;
    }
    return s-tot;
}

ll work(ll wi){
    for(int i = 1;i <= n;i++)
        if(w[i] >= wi)s1[i] = s1[i-1]+v[i],s2[i] = s2[i-1]+1;
        else s1[i] = s1[i-1],s2[i] = s2[i-1];
    ll tot = 0;
    for(int i = 1;i <= m;i++)tot += (s1[r[i]]-s1[l[i]-1])*(s2[r[i]]-s2[l[i]-1]);
    return s-tot;
}

int main(){
    n = read(),m = read(),s = read();
    for(ll i = 1;i <= n;i++){
        w[i] = read(),v[i] = read();
        miv = min(miv,w[i]);
        mav = max(mav,v[i]);
    }
    miv>>=1,mav<<=1;
    for(ll i = 1;i <= m;i++)l[i] = read(),r[i] = read();
    for(ll i = 1;i <= 50;i++){
        ll mid = miv+mav>>1,cur = work(mid);
        if(cur < 0){
            miv = mid;
            if(ansv > -cur)ans = mid,ansv = -cur;
        }
        else{
            mav = mid;
            if(ansv > cur)ans = mid,ansv = cur;
        }
    }
    cout << ansv;
return 0;
}