题解 P1314 【聪明的质监员】

· · 题解

看到这题，哇，那么多区间，肯定是莫队是吧。。/好吧可能只有我是这么想的/

然后哇，大于w的所有数的一些和，线段树对吧。。/好吧只有我是这么想的/

然后洋洋洒洒上百行，，写挂了

于是想到了前缀和

于是莫队+前缀和+卡常+玄学剪枝（最优性）AC

不知道莫队的童鞋看下我对题意的解释吧

题目的式子表示的是在区间[l,r]内的所有j，只要w[j]>W，那么就前面的sigma++,后面的sigma+=v[j]

这样就懂了吧，区间内所有符合条件的产品，求其数量乘上价值和

最后所有区间相加即可

我呢也看了很久，最后想出来了，这样的“好题”最锻(chao)炼(ji)思(keng)维(bi)了

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
using namespace std;
inline ll read()
{
    register char ch=getchar();
    register ll h=0;
    while(ch>'9'||ch<'0')ch=getchar();
    while(ch>='0'&&ch<='9'){h=h*10+ch-'0';ch=getchar();}
    return h;
}
ll n,m,s;
ll ans=1000000000000000;
ll v[200001],w[200001];
ll sqrtn;
ll jzh,slh;//价值和，数量和 
struct qj{
    ll l,r;
}a[200001];
inline int cmp(const qj&a,const qj&b)//分块
{
    if(a.l/sqrtn<b.l/sqrtn)return 1;
    if(a.l/sqrtn>b.l/sqrtn)return 0;
    return a.r<b.r;
}
inline void go_r(ll W,ll x,ll y)
{
    if(x==y)return;
    if(x>y)
    {
        for(register ll i=x;i>=y+1;i--)
            if(w[i]>=W){slh--;jzh-=v[i];}
    }
    else
    {
        for(register ll i=x+1;i<=y;i++)
            if(w[i]>=W){slh++;jzh+=v[i];}
    }
}
inline void go_l(ll W,ll x,ll y)
{
    if(x==y)return;
    if(x>y)
    {
        for(register ll i=x-1;i>=y;i--)
            if(w[i]>=W){slh++;jzh+=v[i];}
    }
    else
    {
        for(register ll i=x;i<=y-1;i++)
            if(w[i]>=W){slh--;jzh-=v[i];}
    }
}
inline ll check(ll k)//以k为标准
{
    a[0].l=1;a[0].r=0;
    slh=0;jzh=0;
    register ll tot=0;
    for(register ll i=1;i<=m;i++)
    {
        go_r(k,a[i-1].r,a[i].r);
        go_l(k,a[i-1].l,a[i].l);
        tot+=slh*jzh;
        if(tot-s>=ans)return s+1;//如果已经超过了s+ans，那么应该下一次搜的时候要把标准放大，使得tot减小
    }
    if(tot>s)ans=ans<(tot-s)?ans:(tot-s);
    else ans=ans<(s-tot)?ans:(s-tot);
    return tot;
}
int main()
{
    n=read();m=read();
    s=read();sqrtn=sqrt(n);
    for(register ll i=1;i<=n;i++)
    {w[i]=read();v[i]=read();}
    for(register ll i=1;i<=m;i++)
    {a[i].l=read();a[i].r=read();}
    sort(a+1,a+m+1,cmp);
    register ll lll=1,rr=1000000;
    while(lll<rr)//mid越大，检验值越小
    {
        register ll mid=(lll+rr)>>1;
        if(check(mid)<s)rr=mid;
        else lll=mid+1;
    }
    printf("%lld\n",ans);
    return 0;
}