文章

25

粉丝

0

获赞

0

访问

244687

头像
分块算法
经验总结
发布于2020年4月21日 21:26
阅读数 8554

 分块:将查询的区间按照左指针按快排序,如果在同一个块中,则按照右指针区间得大小从小到大排序。

左指针l=1,r=0;将左指针移动sqrt(n),右指针n,故O(nsqrt(n)):

Q:小Z的袜子:

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 50010;
typedef long long ll;
ll n, m, a[N], belong[N], l, r, ans, num[N];//num[N]存分子的组合数,belong[N]第i个袜子属于的块数,a[i]存输入的袜子编号,l,r初始化区间
struct node{
	int l, r, id;//查询区间(l,r),id记录查询的顺序,按序输出结果
	ll a, b;//分子分母,每一组查询的分子分母
}maze[N];
ll gcd(ll a, ll b){
	if (b == 0){ return a; }
	else{
		return gcd(b, a%b);
	}
}
bool cmp(node a, node b){//将查询分块
	if (belong[a.l] == belong[b.l]){
		return a.r < b.r;
	}
	else{
	//	return belong[a.l] < belong[b.l];
		return a.l < b.l;
	}
}
void add(int x){
	ans -= num[a[x]] * num[a[x]];
	num[a[x]] += 1;
	ans += num[a[x]] * num[a[x]];
}
void sub(int x){
	ans -= num[a[x]] * num[a[x]];
	num[a[x]] -= 1;
	ans += num[a[x]] * num[a[x]];
}
bool cmp_id(node a, node b){
	return a.id < b.id;//按照查询id先后顺序输出查询结果
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		cin >> a[i];
	}
	ll block = (ll)sqrt((double)n);
	for (int i = 1; i <= n; i++){
		belong[i] = (i - 1) / block + 1;//记录所属块数,用于将查询分块
	}
	for (int i = 1; i <= m; i++){
		cin >> maze[i].l >> maze[i].r;
		maze[i].id = i;
	}
	sort(maze + 1, maze + 1 + m, cmp);
	l = 1, r = 0;
	ans = 0;//记录分子,即可以组成袜子的数
	for (int i = 1; i <= m; i++){
		while (r < maze[i].r){
			add(++r);
		}
		while (r>maze[i].r){
			sub(r--);
		}
		while (l < maze[i].l){
			sub(l++);
		}
		while (l>maze[i].l){
			add(--l);
		}
		if (maze[i].l == maze[i].r){
			maze[i].a = 0; maze[i].b = 1;
			continue;
		}
		maze[i].a = ans - (maze[i].r - maze[i].l + 1);
		maze[i].b = (maze[i].r - maze[i].l + 1)*1LL*(maze[i].r-maze[i].l);
		ll gcdd = gcd(maze[i].a, maze[i].b);
		maze[i].a /= gcdd;
		maze[i].b /= gcdd;

	}
	sort(maze + 1, maze + 1 + m, cmp_id);
	for (int i = 1; i <= m; i++){
		cout << maze[i].a << "/" << maze[i].b << endl;
	}
	return 0;
}

 



登录后发布评论

暂无评论,来抢沙发