D. Frets On Fire(思维+差分+二分)

https://codeforces.com/problemset/problem/1119/D

---

 

题目描述

Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has nn strings, and each string has (10^{18} + 1)(1018+1) frets numerated from 00 to 10^{18}1018 . The fleas use the array s_1, s_2, \ldots, s_ns1​,s2​,…,sn​ to describe the ukulele's tuning, that is, the pitch of the jj -th fret on the ii -th string is the integer s_i + jsi​+j .

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: "How many different pitches are there, if we consider frets between ll and rr (inclusive) on all strings?"

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with nn rows and (10^{18}+1)(1018+1) columns, where the cell in the ii -th row and jj -th column ( 0 \le j \le 10^{18}0≤j≤1018 ) contains the integer s_i + jsi​+j . You are to answer qq queries, in the kk -th query you have to answer the number of distinct integers in the matrix from the l_klk​ -th to the r_krk​ -th columns, inclusive.

输入格式

The first line contains an integer nn ( 1 \leq n \leq 100\,0001≤n≤100000 ) — the number of strings.

The second line contains nn integers s_1, s_2, \ldots, s_ns1​,s2​,…,sn​ ( 0 \leq s_i \leq 10^{18}0≤si​≤1018 ) — the tuning of the ukulele.

The third line contains an integer qq ( 1 \leq q \leq 100\,0001≤q≤100000 ) — the number of questions.

The kk -th among the following qq lines contains two integers l_klk​ ， r_krk​ ( 0 \leq l_k \leq r_k \leq 10^{18}0≤lk​≤rk​≤1018 ) — a question from the fleas.

输出格式

Output one number for each question, separated by spaces — the number of different pitches.

题意翻译

题目背景

Miyako 带着尤克里里琴来到跳蚤王国。她与当地的跳蚤居民成为了好朋友，每天为他们演奏美妙的音乐。

题目描述

作为回报，跳蚤为她做了一个更大的尤克里里琴：它有 nn 个弦，每个弦都有从 00 到 10^{18}1018 的 10^{18}+11018+1 个琴格（用来给琴划分音阶高低）。跳蚤使用数组 s_1, s_2,......,s_ns1​,s2​,......,sn​ 来描述尤克里里琴的品，也就是说，第 ii 个弦上第 jj 个琴格的音调是整数 s_i+jsi​+j。

Miyako 即将离开王国，但跳蚤希望 Miyako 能为它们回答最后一些问题。

第 kk 个问题是：“在所有弦上，琴格 l_klk​ 与琴格 r_krk​（包括 l_klk​，r_krk​）之间有多少个不同的音调？”

Miyako 即将访问蟋蟀王国，没有时间回答所有问题。请你帮助她完成这项任务！

在形式上，给出一个 nn 行 10^{18}+11018+1 列的矩阵，其中第 ii 行（1 \leqslant i \leqslant n1⩽i⩽n）第 jj 列（0 \leqslant j \leqslant 10^{18}0⩽j⩽1018）中的单元格为整数 s_i+jsi​+j。有 qq 个询问，对于第 kk 个询问，你需要回答矩阵中从第 l_klk​ 行到第 r_krk​ 行（包括 l_klk​，r_krk​）的不同整数的数量。

---

 

思路：最开始的时候想一列一列去统计增量，因为到最后增的都是1了嘛.发现这样中间的差值用差分什么的推不出来。

那一行一行去考虑。

先sort变成从小到大去排。

考虑s1对答案的贡献是[s1+l,s1+r]也就是贡献r-l+1;

然后考虑s2对答案的贡献，这样容易发现当s2+l>s1+r的时候贡献是r-l+1（因为两条区间不重合)

那么如果重合的时候贡献就是s2-s1。

这样发现每次统计贡献就是min(r-l+1,si-si-1)。这样当然是O(N)的并且还有m次查询肯定要优化。

si-si-1就用差分去优化，预处理成cnt[i]数组。

if(d[i]>=r-l+1)这时候的贡献就是r-l+1.

else if(d[i]<r-l+1)这时候的贡献就是d[i].

那么中间的分界点就可以用二分去枚举。枚举到了以后后面的a[ ]贡献就是 (r-l+1)*(n-num+1);前面的贡献就是d[1]+.....d[num-1]。这里用前缀和去优化就好了。

这道题的启发：一行一行比较区间重复计算条件和单纯利用(1~r-)-(1~l-1)一列列难以推出增的公式并且整个序列是很长的没法存储，转化到一列列上下区间交集比较贡献就容易多。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL pre[maxn],cnt[maxn],a[maxn];
LL n,q;
LL bsearch(LL x)
{
	LL l=1;LL r=n;
	while(l<r)
	{
		LL mid=(l+r)/2;
		if(cnt[mid]>=x) r=mid;
		else l=mid+1;
	}
	return l;
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  cin>>n;
  for(LL i=1;i<=n;i++) cin>>a[i];
  sort(a+1,a+1+n);
  cin>>q;
  for(LL i=2;i<=n;i++) cnt[i-1]=a[i]-a[i-1];
  sort(cnt+1,cnt+n);//cnt开头下标1，结尾是n-1 
  for(LL i=1;i<=n;i++) pre[i]=pre[i-1]+cnt[i];
  while(q--)
  {
  	LL l,r;cin>>l>>r;
  	LL len=r-l+1;
  	LL num=bsearch(len);//找到d[i]<len的第一个点 
  	LL ans=len*(n-num+1)+pre[num-1];
  	cout<<ans<<endl;
  }
return 0;
}