P5459 [BJOI2016]回转寿司

左手的ㄟ右手 2021-12-10 02:53 158阅读 0赞

[传送门][Link 1]

暴力怎么搞，维护前缀和 $s\[i\]$ ，对于每一个 $s\[i\]$，枚举所有 $j\\in\[0,i-1\]$，看看 $s\[i\]-s\[j\]$ 是否属于 $\[L,R\]$

如果属于就加入答案

$s\[i\]-s\[j\]\\in\[L,R\]$ 等价于 $s\[i\]-s\[j\] \\geqslant L , s\[i\]-s\[j\] \\leqslant R$

即 $s\[i\]-L \\geqslant s\[j\] , s\[i\]-R \\leqslant s\[j\]$

发现对于每一个 $i$ 其实就是问区间 $\[0,i-1\]$ 中权值在 $\[s\[i\]-L,s\[i\]-R\]$ 之间的 $s\[j\]$ 的数量

直接权值树状数组，发现值域太大，所以要离散化

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    typedef long long ll;
    inline int read()
    {
        int x=0,f=1; char ch=getchar();
        while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
        while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }
        return x*f;
    }
    const int N=1e6+7;
    int n,L,R;
    int t[N];
    ll ans,a[N],s[N];//注意long long
    inline void add(int x) { while(x<=n+1) t[x]++,x+=x&-x; }
    inline int ask(int x) { int res=0; while(x) res+=t[x],x-=x&-x; return res; }
    int main()
    {
        n=read(),L=read(),R=read();
        for(int i=1;i<=n;i++) a[i]=s[i]=s[i-1]+read();
        sort(a+1,a+n+2);
        for(int i=0;i<=n;i++)//注意i=0
        {
            int tr=lower_bound(a+1,a+n+2,s[i]-L+1)-a-1;//这个等价于upper_bound(a+1,a+n+2,s[i]-L)-a-1;
            int tl=lower_bound(a+1,a+n+2,s[i]-R)-a;
            ans+=ask(tr)-ask(tl-1);
            add(lower_bound(a+1,a+n+2,s[i])-a);
        }
        printf("%lld\n",ans);
        return 0;
    }
    
    //si-sj>=L  si-L>=sj sj<=si-L
    //si-sj<=R  si-R<=sj sj>=si-R

转载于:https://www.cnblogs.com/LLTYYC/p/11175354.html

[Link 1]: https://www.luogu.org/problemnew/show/P5459