Codeforces Global Round 2 D Frets On Fire
http://codeforces.com/contest/1119/problem/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 (1018+1)(1018+1) frets numerated from 00 to 10181018 . The fleas use the array s1,s2,…,sns1,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 si+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 (1018+1)(1018+1) columns, where the cell in the ii -th row and jj -th column (0≤j≤10180≤j≤1018 ) contains the integer si+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 lklk -th to the rkrk -th columns, inclusive.
Input
The first line contains an integer nn (1≤n≤1000001≤n≤100000 ) — the number of strings.
The second line contains nn integers s1,s2,…,sns1,s2,…,sn (0≤si≤10180≤si≤1018 ) — the tuning of the ukulele.
The third line contains an integer qq (1≤q≤1000001≤q≤100000 ) — the number of questions.
The kk -th among the following qq lines contains two integers lklk ，rkrk (0≤lk≤rk≤10180≤lk≤rk≤1018 ) — a question from the fleas.
Output
Output one number for each question, separated by spaces — the number of different pitches.
Examples
Input
6 3 1 4 1 5 9 3 7 7 0 2 8 17
Output
5 10 18
Input
2 1 500000000000000000 2 1000000000000000000 1000000000000000000 0 1000000000000000000
Output
2 1500000000000000000
题目大意： 有一个n*(10^18+1)的矩阵，给出第一列的n个值，第二列的值等于第一列对应元素的值+1，第三列……有m个询问，问从l列到r列即[l，r]的不同的元素个数。
思路：超详细的题解~耐心看完一定能懂。假设我们第一列元素的值为：1、3、6、7，且查询的l等于0，那么我们来看一张图：
我们发现：从1到3贡献了一个数(2)，从3到6贡献了2个数(4 5)，从6到7贡献了0个数，(再往后的数字就是完全重复的 除了7即初始列的最大值一直在更新)，那么我们可以发现，其实关键点不是数本身，而是数之间的差值(实际上是这个差值再减去1)。因此我们读入初始列，对其进行排序，(对初始列进行排序是为了得到的差值都是正数 同时统计一下初始列中不同的数的个数 )然后把ai-a(i-1)-1的值存到另外一个dis数组中(重复的值只存1次 且我们只存ai-a(i-1)>1的情况 因为从上面的例子可以看出 等于1的时候对答案是没有贡献的)， 因为假设l=0，又我们知道r的值，因此我们遍历dis数组将其与r比较就可以得到不同的数的个数。不懂？那我们来看一下上面的例子，dis数组= {1，2} ，初始列不同的元素个数cnt=4，(这个还不懂的罚你重看)， 当r=1时，答案=4+1+1+1=7，(新出现的数是：2 4 8)；当r=2时，答案=4+1+2+2=9，(新出现的是 2 4 5 8 9)；为什么我把答案分成4部分呢？大家可以再举复杂一点的例子，会发现答案由4部分组成：(1)初始列不同的元素个数 即cnt；(2)遍历dis数组统计的贡献和，即第i个位置的贡献为：min(dis[i]，r)；(3)初始列最大的元素一直在贡献新的值，贡献了r个新的数； 这不是只有3部分吗？第4部分呢？ 其实上面的(2)可以分出来两部分，因为(2)是遍历dis数组得到的答案，但是每个查询都遍历的话会TLE，因此我们需要一种更加高效的求(2)的方法，我们考虑对dis数组进行排序，然后找到dis数组中第一个大于r的值，那么r的左侧的贡献就是：dis[0]+……+dis[r-1]； r的右侧的贡献就是：r+r+……+r(设dis数组有len个元素 则此处有len-r+1个)，这样做的话我们就可以在O(lglen)的复杂度下求出贡献值，不会TLE！(当然 我们还需要一个前缀和数组来优化~)至此，问题基本已经解决，唯一的不足就是，我们假设了l=0，那么我们思考一下l与r的值真的重要吗？其实一点都不重要，重要的是r与l的差值。道理很浅显，求3 4 5 6中不同的元素的个数与求0 1 2 3中不同的元素个数是一样的。(即对原序列均减去3)那么我们把区间平移，即令r-=l不就行了吗。好的，我们再重新理一遍思路：(1)读入初始列进行排序并统计不同的元素个数。(2)计算有效的差值存入dis数组。(3)对dis数组进行排序同时用sum记录其前缀和。(4)读入查询的l和r，得到差值d=r-l，通过upper_bound函数在dis数组中得到位置i，计算答案并输出。
#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
ll a[100005];
ll dis[100005];
ll sum[100005];
int len=0;
ll l,r;
int main()
{
int n,m;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n);
int cnt=1;
for(int i=1;i<n;i++)
{
if(a[i]!=a[i-1])
++cnt;
if(a[i]-a[i-1]>1)
dis[++len]=a[i]-a[i-1]-1;
}
sort(dis+1,dis+1+len);
sum[0]=0;
sum[1]=dis[1];
for(int i=2;i<=len;i++)
sum[i]=sum[i-1]+dis[i];
scanf("%d",&m);
ll d;
int idx=0;
for(int i=0;i<m;i++)
{
scanf("%lld %lld",&l,&r);
d=r-l;
idx=upper_bound(dis+1,dis+1+len,d)-dis-1;
printf("%lld ",cnt+sum[idx]+(len-idx)*d+d);
}
putchar('\n');
return 0;
}