题解

附上我是如何把时间复杂度从O(n²m)优化到O(m²)

大致题意 给出n组(a,b),从中选出两组记为(ai,bi) (aj,bj) （ i可以等于j ) 求满足对范围 0…2M 内的每个值 k 使$ai+aj≤k≤bi+bj$ 有多少种选法

容易想到朴素 维护一个数组ans 枚举所有i,j

$ans[k]+=1，ai+aj<=k<=bi+bj$

时间复杂度是O(n²m） 10分

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N],ans[N];
int main(){
	int m,n;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=a[i]+a[j];k<=b[i]+b[j];k++){
				ans[k]++;
			}
		}
	}
	for(int i=0;i<=2*m;i++)printf("%d\n",ans[i]);
}

可以把

for(int k=a[i]+a[j];k<=b[i]+b[j];k++)ans[k]++;

优化成

ans[a[i]+a[j]]++; ans[b[i]+b[j]+1]--;

即变为O(n²）25分

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],b[N],ans[N];
int main(){
	int m,n;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			ans[a[i]+a[j]]++;
			ans[b[i]+b[j]+1]--;
		}
	}
	for(int i=0;i<=2*m;i++)ans[i]+=ans[i-1],printf("%d\n",ans[i]);
}

从上述代码发现 ai+aj，bi+bj在ans数组里是分开统计的也就是说我们可以对a数组和b数组单独处理 即： 从a数组中得到所有的ai+aj 从b数组中得到所有的bi+bj+1

同时我们发现m很小 也就是（a,b)中有很多重复的元素 如这个样例

5 6
1 2
1 4
2 4
2 5
2 6

​可以抽象成这个问题 a{1，1，2，2，2} 从中选两个数相加（选完自己后还可以选自己） 求不同和的个数

不难得出 当ai+aj为2时 个数为2*2=4

当ai+aj为3时 个数为2*3=6

当ai+aj为4时 个数为3*3=9

于是ans[2]+=4 ans[3]+=6 ans[4]+=9

同理b也一样

于是我们可以统计每个数的个数记为sum

对于a数组中两个数x y ans[x+y]+=sum_a[x]*sum_a[y]

对于b数组中两个数x y ans[x+y+1]-=sum_b[x]*sum_b[y]

于是由O(n²)->O(m²) AC

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
long long a[N],b[N];long long ans[N];
int main(){
	int m,n;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		a[x]++,b[y]++;
	}
	for(int i=0;i<=m;i++)for(int j=0;j<=m;j++)ans[i+j]+=a[i]*a[j],ans[i+j+1]-=b[i]*b[j];
	for(int i=0;i<=2*m;i++)ans[i]+=ans[i-1],printf("%lld\n",ans[i]);
}