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

左指针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先后顺序输出...