首页 > 代码库 > CodeForces 86D（Yandex.Algorithm 2011 Round 2）

CodeForces 86D（Yandex.Algorithm 2011 Round 2）

2024-07-12 03:58:59   221人阅读

思路：莫队算法，离线操作，将所有询问的左端点进行分块（分成sqrt（n） 块每块sqrt（n）个），用左端点的块号进行排序小的在前，块号相等的，右端点小的在前面。 这样要是两个相邻的查询在同一块内左端点每次最多移动sqrt（n） n次的话效率为nsqrt（n） ，对于同一块内右端点为有序的那么最多移动 n次  。总的效率为nsqrt（n） 。 要是相邻的查询不同块 最坏效率为O（n） 因为块最多为sqrt（n）个那么坏效率也为nsqrt（n）。   总的效率就为nsqrt（n）

 

#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include <iostream>#define N 200010#define LL __int64using namespace std;struct node {	int l, r, id;	int pid;} s[N];inline bool cmp(node a, node b) {	return a.id < b.id || a.id == b.id && a.r < b.r;}int a[N];LL ans[N];int cnt[1000100];LL sum = 0;inline void add(LL x) {	sum += x * (cnt[x] << 1 | 1);	cnt[x]++;}inline void dec(LL x) {	sum += x * (1 - (cnt[x] << 1));	cnt[x]--;}int main() {	int i, j, k, n, m, one;	memset(cnt, 0, sizeof(cnt));	scanf("%d%d", &n, &m);	one = sqrt(n * 1.0);	for (int i = 1; i <= n; ++i)		scanf("%d", &a[i]);	for (int i = 0; i < m; ++i) {		scanf("%d%d", &s[i].l, &s[i].r);		s[i].id = s[i].l / one;		s[i].pid=i;	}	sort(s, s + m, cmp);	int l, r;	l = s[0].l;	r = s[0].r;	for (int i = s[0].l; i <= s[0].r; ++i)		add(a[i]);	ans[s[0].pid]=sum;	for (i = 1; i < m; ++i) {		while(r<s[i].r)add(a[++r]);		while(r>s[i].r)dec(a[r--]);		while(l<s[i].l)dec(a[l++]);		while(l>s[i].l)add(a[--l]);		ans[s[i].pid]=sum;	}	for(int i=0;i<m;++i)		printf("%I64d\n",ans[i]);	return 0;}

　　


联系
我们