莫队

这题是个莫队模板题，今天学习了一下莫队，莫队用到了分块。莫队的巧妙之处就在于它的排序+转移。
这题是个不带修莫队，先按照询问的左端点排序，左端点在同一区间再按照右端点排序，通常 $l$ 和 $r$ 转移对答案带来的影响可以预先推出来，然后实现了 $O(1)$转移 ，$cnt[x]$表示$x$的个数比如这题的答案就是

$\dfrac{(\sum\ C_{cnt[x]}^2)}{ C{2 \choose r-l+1}}$

化简一下就是

$\dfrac{ (\sum\ ({cnt[x]})^2 ) -(r-l+1) }{ (r-l+1)(r-l) }$

如果增加数，转移的时候就是增加了 $(cnt[x]+1)^2 - (cnt[x])^2$

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
using namespace std; 
const int N = 5e4+10;
int a[N], cnt[N],b[N];
int n, m,block;
ll ans;
ll gcd(ll a, ll b)
{
	if (!b) return a;
	return gcd(b, a%b);
}
struct query{
	int id, l, r;
	int aa, bb;
}q[N];
bool cmp1(query o1, query o2)
{
	if (b[o1.l] != b[o2.l]) return o1.l < o2.l;
	return o1.r < o2.r;
}
bool cmp2(query o1, query o2)
{
	return o1.id < o2.id;
}
void update(int pos,int val)
{
	ans -= (cnt[a[pos]] * cnt[a[pos]]);
	cnt[a[pos]] += val;
	ans += (cnt[a[pos]] * cnt[a[pos]]);
	
}
int main()
{
	scanf("%d%d", &n, &m);
	block = sqrt(n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		b[i] = (i - 1) / block + 1;
	}
	for (int i = 1; i <= m; i++)
	{
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + m + 1,cmp1);
	int l = 1, r = 0;
	for (int i = 1; i <= m; i++)
	{
		while (l < q[i].l) update(l++, -1);
		while (l>q[i].l) update(--l, 1);
		while (r < q[i].r) update(++r, 1);
		while (r>q[i].r) update(r--, -1);
		if (q[i].l == q[i].r){
			q[i].aa = 0;
			q[i].bb = 1;
			continue;
		}
		ll aa = ans - (q[i].r - q[i].l + 1);
		ll bb = (q[i].r - q[i].l + 1LL)*(q[i].r - q[i].l);
		ll d = gcd(aa, bb);
		q[i].aa = aa / d, q[i].bb = bb / d;
	}
	sort(q + 1, q + m + 1, cmp2);
	for (int i = 1; i <= m; i++)
	{
		printf("%d/%d\n", q[i].aa, q[i].bb);
	}
	return 0;
}

带修改的怎么处理呢？
可以再增加一个时间记录最近更改的时间，这个时侯为减小复杂度，排序的时候就要变一下，分块的大小也要变。（块的大小很影响时间复杂度），这样我们每次转移的时候$l,r,t$ 一起转移。具体可以看代码。

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<cstring>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long 
using namespace std; 
const int N = 5e4+10;
const int M = 1e6 + 10;
int a[N], cnt[M],b[N],Ans[N];
int n, m,block,T,tot, ans;
int l, r;
struct query{
	int id, l, r,t;
}q[N];
struct change{
	int pos, val, pre;
}R[N];
bool cmp1(query o1, query o2)
{
	if (b[o1.l] == b[o2.l]) { 
		if (b[o1.r] == b[o2.r]) 
			return o1.t < o2.t;
		return o1.r < o2.r; 
	}
	return o1.l < o2.l;
}
void add(int pos)
{
	if (cnt[a[pos]]++ == 0) ans++;
}
void del(int pos)
{
	if (--cnt[a[pos]]==0) ans--;
}
void update(int t)
{
	if (R[t].pos <= r&&R[t].pos >= l){
		if (cnt[R[t].val]++ == 0)ans++;
		if (--cnt[a[R[t].pos]] == 0) ans--;
	}
	swap(a[R[t].pos], R[t].val);
}
int main()
{
	scanf("%d%d", &n, &m);
	block = pow(n,2.0/3.0);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		b[i] = (i - 1) / block + 1;
	}
	for (int i = 1; i <= m; i++)
	{
		char op[3];
		scanf("%s", op);
		if (op[0] == 'Q')
		{
			++tot;
			scanf("%d%d", &q[tot].l, &q[tot].r);
			q[tot].t = T;
			q[tot].id = tot;
		}
		else if (op[0] == 'R')
		{
			++T;
			scanf("%d%d", &R[T].pos, &R[T].val);
		}
	}
	sort(q + 1, q + tot + 1,cmp1);
	l = 1, r = 0;
	int t = 0;
	for (int i = 1; i <= tot; i++)
	{
		while (t < q[i].t) update(++t);
		while (t>q[i].t) update(t--);
		while (l < q[i].l) del(l++);
		while (l>q[i].l) add(--l);
		while (r < q[i].r) add(++r);
		while (r>q[i].r) del(r--);
		Ans[q[i].id] = ans;
	}
	for (int i = 1; i <= tot; i++)
		printf("%d\n", Ans[i]);
	return 0;
}