洛谷 P1314 聪明的质监员 —— 二分

题目：https://www.luogu.org/problemnew/show/P1314

显然就是二分那个标准；

当然不能每个区间从头到尾算答案，所以要先算出每个位置被算了几次；

不知为何自己第一想法是把符合要求的位置插入树状数组再遍历区间得到该区间内的个数然后在其左右端点差分最后遍历位置时一边计算每个位置的次数；

但其实用前缀和就可以了...而且前缀和比上面那个快好多...

调了好半天，才发现 ans 的初值不能习惯性地赋成 0x3f3f3f3f，那个才是个 int 范围内的...

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define mid ((L+R)>>1)

using namespace std;

typedef long long ll;

int const maxn=2e5+;

int n,m,mx,w[maxn],v[maxn],f[maxn],l[maxn],r[maxn],d[maxn],num[maxn];

ll ans,s,sum[maxn];

ll rd()

{

    ll ret=,f=; char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

    while(ch>=''&&ch<='')ret=(ret<<3ll)+(ret<<1ll)+ch-'',ch=getchar();

    return f?ret:-ret;

}

void add(int x){for(;x<=n;x+=(x&-x))f[x]++;}

int query(int x){int ret=; for(;x;x-=(x&-x))ret+=f[x]; return ret;}

ll work(int x)

{

    ll ret=;

//    memset(f,0,sizeof f);

//       memset(d,0,sizeof d);

//    for(int i=1;i<=n;i++)if(w[i]>=x)add(i);

//    for(int i=1;i<=m;i++)

//    {

//        int k=query(r[i])-query(l[i]-1);

//        printf("l=%d r=%d k=%d\n",l[i],r[i],k);

//        d[l[i]]+=k; d[r[i]+1]-=k;

//    }

//    for(int i=1,nw=0;i<=n;i++)

//    {

//        nw+=d[i];

//        if(w[i]>=x)ret+=(ll)v[i]*nw;

//        printf("i=%d ret=%lld\n",i,ret);

//    }

    memset(sum,,sizeof sum);

    memset(num,,sizeof num);

    for(int i=;i<=n;i++)

    {

        num[i]=num[i-]+(w[i]>=x);

        sum[i]=sum[i-]+(w[i]>=x?v[i]:);

//        printf("num[%d]=%d sum[%d]=%d\n",i,num[i],i,sum[i]);

    }

    for(int i=;i<=m;i++)

        ret+=(sum[r[i]]-sum[l[i]-])*(num[r[i]]-num[l[i]-]);

    return ret;

}

int main()

{

    n=rd(); m=rd(); s=rd();

    for(int i=;i<=n;i++)w[i]=rd(),v[i]=rd(),mx=max(mx,w[i]);

    for(int i=;i<=m;i++)l[i]=rd(),r[i]=rd();

    int L=,R=mx+; ans=1e13;

    //ans=inf;

    while(L<=R)

    {

        ll ret=work(mid);

//        printf("ret=%lld mid=%d L=%d R=%d\n",ret,mid,L,R);

        if(ret>=s)

        {

//            if(ans<=ret-s)break;

            ans=min(ans,ret-s); L=mid+;

        }

        else

        {

//            if(ans<=s-ret)break;

            ans=min(ans,s-ret); R=mid-;

        }

    }

    printf("%lld\n",ans);

    return ;

}

洛谷 P1314 聪明的质监员 —— 二分的相关教程结束。