Loading...

题解 CF1119D Frets On Fire

check评论:0 条 remove_red_eye浏览量:345 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-04-11

真心一道简单题...省选也过分了

考虑到第$i$行到第$j$行的出现数字个数就等于第$1$行到第$j-i+1$行的出现数字个数,所以只需要考虑一开始的数即可

然后考虑的这个玩意不太好维护,我们换个思路

比如第一根弦上的数字$1\ 3\ 4\ 5\ 9$,会发现比较好维护的是$1-9$九个数减去没有出现过的数字$2\ 6\ 7\ 8$

那只要考虑两两数之间作差即可

比如对应上一个例子,我们弄$3$行,会发现是这样的
$\begin{matrix}1\ 3\ 4\ 5\ 9\\2\ 4\ 5\ 6\ 10\\ 3\ 5\ 6\ 7\ 11\end{matrix}$

看得出来,在相邻的差小于$4$的数中,空隙都被填满了

所以只需要先预处理两两间差值的前缀和,然后查询时二分最小的大与询问区间长度的差值即可

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,a[100010],maxdel,del;
int d[100010],sum[100010];
main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+n+1);
    del=a[n]-a[1];
    for(int i=2;i<=n;i++)
    {
        maxdel=max(maxdel,a[i]-a[i-1]);
        d[i]=a[i]-a[i-1]-1;
    } 
    sort(d+2,d+n+1);
    for(int i=2;i<=n;i++)
    {
        sum[i]=sum[i-1]+d[i];
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++)
    {
        int l,r;
        scanf("%lld%lld",&l,&r);
        int ans=a[n]+r-l-a[1]+1;
        if(maxdel<(r-l+1))
        {
            printf("%lld\n",ans);
        }
        else
        {
            int qaq=lower_bound(d+2,d+n+1,(r-l+1))-d;
            ans-=(sum[n]-sum[qaq-1]-(r-l)*(n-qaq+1));
            printf("%lld\n",ans);
        }
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名