526互联

Codeforces Global Round 2

发布时间 2023-10-06 16:47:53作者: gan_coder

C题结论就是每行每列不同的个数必须是偶数。

D题首先注意到对于长度相同的询问，答案都是一样的。
同时相同的s可以直接丢掉。

那么我们将s排序之后，将相邻的差再进行排序，然后将询问从小到大处理。
相当于是将这些段拼接在一起。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#define A puts("Yes")
#define B puts("No")
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (int (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e5+5;
struct node{
	ll l,id;
};
struct key{
	ll x,y,id;
};
key b[N];
node d[N];

ll a[N],c[N],n,q,ans[N];
ll x,y,sum,tot;
bool cmp(node a,node b){
	return a.l<b.l;
}
bool cmp2(key a,key b){
	return a.y-a.x<b.y-b.x;
}
int main()
{
//	freopen("data.in","r",stdin);
	scanf("%lld",&n);
	fo(i,1,n) scanf("%lld",&a[i]);
	
	sort(a+1,a+n+1);
	n=unique(a+1,a+n+1)-(a+1);
	
	fo(i,1,n-1) b[i]=(key){a[i],a[i+1],i};
	sort(b+1,b+n,cmp2);
	
	scanf("%lld",&q);
	fo(i,1,q){
		scanf("%lld %lld",&x,&y);
		d[i]=(node){y-x+1, i}; 
	}
	
	sort(d+1,d+q+1,cmp);
 	
 	tot=n;
	int j=1;
	fo(T,1,q){
		while (j<n && b[j].y-b[j].x<=d[T].l)  {
			sum+=b[j].y-b[j].x;		
			j++;
			tot--;
		}
		
		ans[d[T].id]=tot*d[T].l+sum;
	}
	
	fo(i,1,q) printf("%lld ",ans[i]);
	
	return 0;
}