Codeforces 1119D(差分)

题面

传送门

分析

先考虑\(O(nk)\)的做法，先按s从小到大排序,每个串的数显然形成了n个连续区间\([s_i+l,s_i+r]\)，且这些区间的左端点升序排列，然后把区间合并就可以知道有多少个不同的数了

然后考虑优化

对于s[i]产生的区间，我们考虑s[i]和s[i+1]产生的区间之间的间隔

若\(s_i+r \leq s_{i+1}+l\)，即\(r-l \leq s_{i+1}-s_i\)

则说明s[i]产生的区间和s[i+1]产生的区间不相交，答案增加\((s_i+r)-(s_i+l)+1=r-l+1\)

否则说明\(s_i+l\)到\(s_{i+1}+l\)被占满了，答案增加\(s_{i+1}-s_i\)

定义差分\(d_i=s_{i+1}-s_i\)

综上，我们要求\(\sum \begin{cases} r-l+1,r-l \leq d_i \\ d_i,r-l > d_i\end{cases}\)

但是这样还是O(n)的，如何优化？

我们发现这个式子与区间的顺序无关，因此我们按\(d_i\)排序，每次就可以二分找到小于\(d_i\)的区间的位置,然后前缀和就可以了

注意我们刚刚讨论的都是前n-1个区间，最后一个区间直接加上他的长度就可以了

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 100005

using namespace std;

int n,m;

long long s[maxn];

long long d[maxn];

struct node{

	long long dif;

	int id;

	friend  bool operator < (node p,node q){

		return p.dif<q.dif;

	}

}a[maxn];

long long sumd[maxn];

int bin_search(int l,int r,long long k){

	int mid,ans=0;

	while(l<=r){

		mid=(l+r)>>1;

		if(a[mid].dif<=k){

			ans=mid;

			l=mid+1;

		}else r=mid-1;

	}

	return ans+1;

}

long long solve(long long l,long long r){

	int pos=bin_search(1,n-1,r-l);

	long long ans=0;

	if(pos-1>0) ans+=sumd[pos-1];

	if(pos<n){

		ans+=(n-pos)*(r-l+1);

	}

	ans+=(r-l+1);

	return ans;

}

int main(){

	scanf("%d",&n);

	for(int i=1;i<=n;i++) scanf("%I64d",&s[i]);

	sort(s+1,s+1+n);

	for(int i=1;i<n;i++){

		d[i]=s[i+1]-s[i];

	}

	for(int i=1;i<n;i++){

		a[i].dif=d[i];

		a[i].id=i;

	}

	sort(a+1,a+n);

	for(int i=1;i<n;i++){

		sumd[i]=sumd[i-1]+a[i].dif;

	}

	long long l,r;

	scanf("%d",&m);

	for(int i=1;i<=m;i++){

		scanf("%I64d %I64d",&l,&r);

		printf("%I64d\n",solve(l,r));

	}

}

巴特西

Codeforces 1119D(差分)

题面

分析

代码

最新文章

热门文章