Accelerator‘s Blog

感觉老是在博客上写计划没什么意思，而且写点总结和题解应该也有助于加深印象，所以从今天开始要频繁更新了~

今天听yxj讲了一整天的序列相关，东西真是太多了，我想应该要把这些东西好好消化一下= =

首先是莫队算法。

莫队算法是对于一个长度为n的序列A(A1,A2...An)，m个询问{L,R},回复(AL,AR)中随机取出两个数相同的概率。（题目详情请见BZOJ2038小Z的袜子）

其思想这里不再赘述，请见论文。。。

据说曼哈顿MST实现的现在并不常用了，而分块是比较常用的思想。

复杂度：O(n sqrt(n)log n)

代码实现：

/*
莫队算法 + 分块
详情见论文 
曼哈顿距离MST不想写QAQ 
*/
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 50000 + 5
typedef long long ll;
int c[maxn],num[maxn],n,m,uni,L = 1,R = 0;ll temp = 0;
struct Ans{
	long long a,b;
}ans[maxn];
struct Node{
	int l,r,id;	
}node[maxn];

inline ll gcd(ll a,ll b){
	if(!b)return a;
	return gcd(b,a % b);
}
inline void reduce(ll &a,ll &b){
	ll tmp = gcd(a,b);
	a /= tmp;b /= tmp;
	return;
}
inline bool cmp(Node a,Node b){
	if(a.l / uni != b.l / uni) return a.l / uni < b.l / uni;
	return a.r < b.r;
}

int main()
{
	memset(num,0,sizeof(num));
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n; i++)scanf("%d",&c[i]);
	for(int i = 1;i <= m; i++){
		node[i].id = i;
		scanf("%d%d",&node[i].l,&node[i].r);
	}
	uni = (int)sqrt(n);
	sort(node + 1,node + m + 1,cmp);
	
	for(int i = 1;i <= m; i++){
		while(R < node[i].r){
			R ++;
			temp -= (ll) num[c[R]] * num[c[R]];
			num[c[R]] ++;
			temp += (ll) num[c[R]] * num[c[R]];
		}
		while(R > node[i].r){
			temp -= (ll) num[c[R]] * num[c[R]];
			num[c[R]] --;
			temp += (ll) num[c[R]] * num[c[R]];
			R --;
		}
		while(L < node[i].l){
			temp -= (ll) num[c[L]] * num[c[L]];
			num[c[L]] --;
			temp += (ll) num[c[L]] * num[c[L]];
			L ++;
		}
		while(L > node[i].l){
			L --;
			temp -= (ll) num[c[L]] * num[c[L]];
			num[c[L]] ++;
			temp += (ll) num[c[L]] * num[c[L]];
		}
		ans[node[i].id].a = temp - (R - L + 1);
		ans[node[i].id].b = (ll) (R - L + 1) *(R - L);
		reduce(ans[node[i].id].a,ans[node[i].id].b);
	}
	
	for(int i = 1;i <= m; i++)printf("%lld/%lld\n",ans[i].a,ans[i].b);
	return 0;
}