D. Frets On Fire 【二分，前缀和】（Codeforces Global Round 2）

佚名 6年前 (2019-04-09) 随笔 1846人围观抢沙发百度已收录

题目传送门：http://codeforces.com/contest/1119/problem/D

D. Frets On Fire

time limit per test

1.5 seconds

memory limit per test

256 megabytes

input standard input output standard output

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.

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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 Copy

6
3 1 4 1 5 9
3
7 7
0 2
8 17

output Copy

5 10 18

input Copy

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

output Copy

2 1500000000000000000

Note

For the first example, the pitches on the 66 strings are as follows.

Frets1:s2:s3:s4:s5:s6:031415914252610253637113647481247585913586961014697107111571081181216…………………Fret01234567…s1:345678910…s2:12345678…s3:4567891011…s4:12345678…s5:56789101112…s6:910111213141516…

There are 55 different pitches on fret 77 — 8,10,11,12,168,10,11,12,16.

There are 1010 different pitches on frets 0,1,20,1,2 — 1,2,3,4,5,6,7,9,10,111,2,3,4,5,6,7,9,10,11.

题意概括：

有一个 N*（10^18) 的矩阵，题目给出 N 和矩阵 N 行的首元素，后面的元素都是前一个元素+1；

Q次查询，询问 [ L, R ] 列有多少个不同的元素（所有行）。

解题思路：

很容易想到，每一行的贡献就是产生小于其他行首元素的值。

因为各行的元素都是加一递增，所以查询 [ L, R ] 和查询 [ 0, R-L+1 ] 是等效的！！！

那么我们就可以先对首元素排一个序，这样相邻两行的差就是前一行所能做的贡献了。

例如排序后是：

那么第一行所能做的贡献就是 2-1 = 1；（小于其他行首元素的也就只有 1 了）

第二行的贡献就是 2-2 = 0, 其实它跟第三行完全一样...

第三行的贡献 5-2 = 3 （2， 3， 4）；

后面类似.

但仅仅是这样，每次查询还是要遍历所有行，复杂度 O(N*Q)，怂了...

频繁的区间查询，看到网上有大佬莽了线段树...

而我只能学习处理一下前缀和了

首先对每行所能做的贡献排一个序

sum[ i ] 为前 i 行所能做出的贡献，前面已经说过查询区间可以等效转移。

那么 R = R-L+1; 在行贡献里二分查找不大于 R 的位置 t，

那么 t 前面的都不比 R 大，也就是说每一行的贡献都不会超标，直接累加，而前面已经处理出前缀和，O(1)解决前面的部分。

后面的都比 R 大，虽然他们贡献很多，但是超标了，每行我只要 R 个（因为只有 R 列），那么这样的有多少行呢有（ N-t )行

AC code：

D. Frets On Fire 【二分，前缀和】（Codeforces Global Round 2）随笔第1张

 1 #include <set>
 2 #include <map>
 3 #include <string>
 4 #include <cstdio>
 5 #include <vector>
 6 #include <iostream>
 7 #include <algorithm>
 8 #define mem(i, j) memset(i, j, sizeof(i))
 9 #define inc(i, j, k) for(LL i = j; i <= k; i++)
10 #define rep(i, j, k) for(LL i = j; i < k; i++)
11 #define gcd(i, j) __gcd(i, j)
12 #define INF 0x3f3f3f3f
13 #define LL long long
14 using namespace std;
15 const int MAXN = 2e5+10;
16 LL num[MAXN];
17 LL sum[MAXN];
18 LL N, Q;
19 LL L, R;
20 vector<LL>ans;
21 int main()
22 {
23     scanf("%I64d", &N);
24     inc(i, 1, N){ scanf("%I64d", &num[i]);}
25     sort(num+1, num+1+N);
26 
27     rep(i, 1, N) num[i] = num[i+1]-num[i];
28     sort(num+1, num+N);
29     rep(i, 1, N) sum[i] = sum[i-1]+num[i];
30     LL tp;
31     scanf("%I64d", &Q);
32     while(Q--){
33         scanf("%I64d %I64d", &L, &R);
34         R = R-L+1; L = 0;
35         tp = upper_bound(num+1, num+N, R)-num-1;
36         ans.push_back(sum[tp]+(N-tp)*R);
37     }
38     for(int i = 0; i < ans.size(); i++){
39         printf("%I64d ", ans[i]);
40     }
41 
42     return 0;
43 }