题解 P1314 【聪明的质监员】

· · 题解

相对于楼上的主席树大佬我觉得我还是好菜啊

二分的性质楼上已经讲过了，那我再来讲讲怎么统计区间和，一开始没有想到那么巧妙的方法，直接用了个树状数组。

众所周知，树状数组可以单点修改区间查询，对于每个w[I]>=W，把sum_n+1,把sum_all+w[i],最后直接区间查询即可，开始时memset一下。

还有一点小细节，这道题要开longlong，答案初始值一定不能赋成0x3f3f3f3f要赋值成0x3f3f3f3f3f3f，因为0x3f3f3f3f太小了。。。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int g[200020],gl[200020],w[200020],v[200020],l[200020],r[200020];
int n,m,s,lmin=0x3f3f3f3f3f3f,rmax,ans=0x3f3f3f3f3f3f;
#define rg register
inline int read(){
    rg char ch=getchar();
    rg int x=0,f=0;
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
int lb(int x){
    return x&-x;
}
void add(int x,int *g,int d){
    for(int i=x;i<=n;i+=lb(i)){
        g[i]+=d;
    }
}
int ask(int x,int *g){
    int sum=0;
    for(int i=x;i;i-=(lb(i))){
        sum+=g[i];
    }
    return sum;
}
bool check(int x){
    memset(g,0,sizeof g);
    memset(gl,0,sizeof gl);
    for(int i=1;i<=n;++i){
        if(w[i]>=x){
            add(i,g,1);
            add(i,gl,v[i]);
        }
    }
    int sum=0;
    for(int rl,rr,i=1;i<=m;++i){
        rr=ask(r[i],gl)-ask(l[i]-1,gl);
        rl=ask(r[i],g)-ask(l[i]-1,g);
        sum+=rr*rl;
    }
    ans=min(ans,llabs(sum-s));
    if(sum>s) return true;
    return false;
}
signed main(){
    n=read();m=read(),s=read();
    for(int i=1;i<=n;++i) w[i]=read(),v[i]=read(),lmin=min(lmin,w[i]),rmax=max(w[i],rmax);
    for(int i=1;i<=m;++i) l[i]=read(),r[i]=read();
    int l=lmin-1,r=rmax+1,mid;
    while(l<=r){
        mid=l+r>>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}