Codeforces Global Round 2 D.Frets On Fire

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

题意：

        有一个n行1e18+1列的矩阵，给定第一列，随后每个数按行以1的速度递增。之后k个询问，问第x列和第y列（相距len=y-x+1）的所有行共计有多少个不同的数。

思路：

        第一步，排序。

        不难想到求两两行首之间的差值c[i]，如果c[i]不小于len，ans+=len，否则ans+=c[i]；按此法答案肯定是对的，但是哪怕unique后依旧是超时的。

        故而我们不妨再次对c数组排序，以便于找到第一个c[id]不小于len。此时如果i>=id,必然ans+=len，简之ans+=len*(n-len)；而对于i<id，必然是互有牵连，依次相加的，所以是s[id-1]+len。

AC代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll a[100010];
ll c[100010];
ll s[100010];
int main()
{
    int n,k;
    c[0]=s[0]=0;
    cin>>n>>a[0];
    for(int i=1;i<n;i++) cin>>a[i];
    sort(a,a+n);
    n=unique(a,a+n)-a;
    for(int i=1;i<n;i++) c[i]=a[i]-a[i-1];
    sort(c+1,c+n);
    for(int i=1;i<n;i++) s[i]=s[i-1]+c[i];
    ll ans;
    cin>>k;
    while(k--)
    {
        ans=0;
        ll x,y;
        cin>>x>>y;
        ll len=y-x+1;
        int id=lower_bound(c+1,c+n,len)-c;
        ans+=len+(n-id)*len+s[id-1];
        if(k==0) cout<<ans<<endl;
        else cout<<ans<<' ';
    }
    return 0;
}