CF1119D Frets On Fire

Description

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 n strings, and each string has (1018+1) frets numerated from 0 to 1018. The fleas use the array s1,s2,…,sn to describe the ukulele's tuning, that is, the pitch of the j-th fret on the i-th string is the integer si+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 l and r (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 n rows and (1018+1) columns, where the cell in the i-th row and j-th column (0≤j≤1018) contains the integer si+j. You are to answer q queries, in the k-th query you have to answer the number of distinct integers in the matrix from the lk-th to the rk-th columns, inclusive.

Input

The first line contains an integer n (1≤n≤100000) — the number of strings.

The second line contains n integers s1,s2,…,sn (0≤si≤1018) — the tuning of the ukulele.

The third line contains an integer q (1≤q≤100000) — the number of questions.

The k-th among the following q lines contains two integers lk，rk (0≤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个以ai开头，依次+1的数列，问在每个数列中去li~ri项，总共有多少不相同的项

思路：
li与ri怎么取并没有意义，只有长度才有意义。
排序后求差，当长度-1>=两相邻数之差时,小的数将没有贡献。
Ⅰ 用离散化的方法，对差排序后对其进行叠加及保存(dxr用的<1>，且省去了离散化）
Ⅱ <1> c[i] = b[i] + c[i-1] (b是差的排序数组）
    前后两数之差大于len的，都有贡献，小于len的全体，有c[i]的贡献
Ⅱ <2> ans[num[i]]=ans[num[i-1]]+tot(num[i]-num[i-1]) (tot当前仍有贡献的数的个数)，用rec[i]来保存)
    out[k]=ans[num[pos]]+(res[num[pos]])*(len-num[pos])
    所求 = num[i]的总贡献+(len-num[i])间有效数个数长度

DXR <1> :

//总的来说，就是差大于len的，都有贡献，小于len的全体，有c[i]的贡献
//有一个极大的好处，就是没有用到离散化的知识点
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef unsigned long long ull;
const int NN = 110000;
int n, num;
ull b[NN], c[NN], tmp, h, len, l, r, ans, m, a[NN];

bool cmp(ull a, ull b)
{
    return a < b;
}

int main()
{
    //freopen("1.in", "r", stdin);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%llu", &a[i]);
    }
    //首先对a排序
    sort(a + 1, a + n + 1, cmp);

    num = 0;
    for (int i = 2; i <= n; i++)
        if (a[i] - a[i - 1])
            b[++num] = a[i] - a[i - 1]; //求两个大小相邻的，不同的数字之间（去重）的差
    sort(b + 1, b + num + 1, cmp);
    //对差排序，求部分和（因为差<len的所有点都有部分重复，需要减去）
    c[0] = 0;
    for (int i = 1; i <= num; i++)
        c[i] = b[i] + c[i - 1];
    //len到b[i]时，该数与该数-1有b[i]未重合
    //c[i]表示到第i个数时，如果len>=b[i]，前面所有数的获得的有效数的总数
    /*
    for (int i=1; i<=n; i++) printf("%d ", a[i]);
    printf("\n");
    for (int i=1; i<=num; i++) printf("%d ", b[i]);
    printf("\n");
    for (int i=1; i<=num; i++) printf("%d ", c[i]);
    printf("\n");
    */
    scanf("%d", &m);
    while (m--)
    {
        scanf("%llu%llu", &l, &r);
        len = r - l + 1; //由题目，最终答案与起点终点无关，至于起点与终点之间的距离有关
        //由题, 每个点与上一个点重复的个数=len-它与上一个点的差（若差>=len, 则无重复点）
        //num是差的个数，有效数的总数为num+1
        ans = (num + 1) * len;                            //先将每个数字可以引出的新数都算上（很可能中间有重复的）
        tmp = lower_bound(b + 1, b + num + 1, len) - b; //找到比len小的最大的差，即为（tmp-1），
        ans -= len * (tmp - 1) - c[tmp - 1];
        //减去重复的个数（每个点仅考虑与上一个点重复的）
        //假设所有<len的数都产生了重复，全部删去，再补上实际上未产生重复的
        //printf("\n%llu\n", tmp);

        printf("%llu ", ans);
    }
    return 0;
}

MS <1> :

//离线完成，极大的降低了复杂度
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<P, int> PP;
const int maxn = 1e5 + 100;
ll a[maxn], b[maxn];
P ans[maxn];
PP q[maxn];
bool cmp(PP p1, PP p2)
{
    if (p1.first.second - p1.first.first < p2.first.second - p2.first.first)
        return 1;
    else
        return 0;
}
bool cmp1(PP p1, PP p2)
{
    if (p1.second < p2.second)
        return 1;
    else
        return 0;
}
int main()
{
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    for (int i = 0; i < n - 1; i++)
        b[i] = (a[i + 1] - a[i]);
    sort(b, b + n - 1);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++)
    {
        cin >> q[i].first.first >> q[i].first.second;
        q[i].second = i;
    }
    sort(q, q + t, cmp);
    ll now = 0, coun = 0;
    for (int i = 0; i < t; i++)
    {
        ll cha = q[i].first.second - q[i].first.first + 1;
        while (coun != n - 1 && cha >= b[coun])
        {
            now += b[coun];
            coun++;
        }
        ans[i].first = q[i].second;
        ans[i].second = now + cha * (n - coun);
    }
    sort(ans, ans + t);
    for (int i = 0; i < t; i++)
    {
        cout << ans[i].second << " ";
    }
}

YZM <2> :

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef long long ll;
int n, q, tot;
ll s[maxn];
ll l, r, len;
map<ll, ll> vis, res, ans;
ll num[maxn], cnt;
ll out[maxn];
int main()
{
    cin >> n;
    tot = n;
    for (int i = 1; i <= n; ++i)
        scanf("%lld", &s[i]);
    sort(s + 1, s + n + 1);
    for (int i = 1; i < n; ++i)
    {
        ll p = s[i + 1] - s[i];
        if (!p)
            tot--;
        else if (!vis[p])
            num[++cnt] = p; //用num保存所有的数
        vis[p]++;
    }
    //for(map<ll,ll>::iterator it=vis.begin();it!=vis.end();it++)
    //printf("%I64d:%I64d\n",it->first,it->second);
    sort(num + 1, num + cnt + 1);
    ans[0] = num[0] = 0;
    for (int i = 1; i <= cnt; ++i)
    {
        ans[num[i]] = ans[num[i - 1]] + tot * (num[i] - num[i - 1]);
        //到num[i]这个数为止，所有数的贡献=上一段的贡献+num[i-1]+1到num[i]间有效数的贡献
        //cout<<i<<' '<<ans[num[i]]<<endl;
        res[num[i - 1]] = tot;
        tot -= vis[num[i]]; //tot为下一段中仍有贡献的数的个数
    }
    res[num[cnt]] = tot;
    //for(int i=0;i<=cnt;++i)
    //printf("->%I64d:%I64d + %I64d\n",num[i],ans[num[i]],res[num[i]]);
    scanf("%d", &q);
    for (int k = 1; k <= q; ++k)
    {
        scanf("%lld%lld", &l, &r);
        len = r - l + 1;
        int pos = upper_bound(num, num + cnt + 1, len) - num;
        pos--; //num[pos]<=len
        //cout<<pos<<endl;
        //printf("pos:%d\n",pos);
        //printf("v:%I64d +:%I64d\n",ans[num[pos]],res[num[pos]]);
        out[k] = ans[num[pos]] + (res[num[pos]]) * (len - num[pos]);
    }
    for (int k = 1; k <= q; ++k)
        printf("%lld ", out[k]);
    return 0;
}