http://www.lydsy.com/JudgeOnline/problem.php?id=2038
题意：多次询问区间内取出两个相同颜色的种类数
思路：由于不是在线更新，那么可以进行离线查询，而且当知道了[l,r]的答案，且能在O（1）的条件下得知[l-1,r],[l+1,r],[l,r+1],[l,r-1]的答案，那么就能使用莫队算法了。 大致上，将区间分块，由于n=a+b>=a*b，显然将区间开平方根是最优的，我们先将询问保存，按照块序第一优先，再考虑右端点进行排序。再来，使用cnt[]来记录当前颜色出现的次数，当得到[l,r]后，再考虑加入[l-1,r] ,[l,r+1]，对答案\(ans-=cnt[col[l-1]]^2,ans+=(cnt[[col[l-1]]+1)^2 \)如果是缩小区间，那么反之。
/** @Date : 2016-12-07-21.28* @Author : Lweleth (SoungEarlf@gmail.com)* @Link : https://github.com/* @Version :*/#include<bits/stdc++.h>
#define LL long long
#define PII pair
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8;LL col[N];
int blc[N];
int cnt[N];
struct yuu
{LL l, r;int id;LL a, b;
}q[N];int cmp(yuu a, yuu b)
{if(blc[a.l] == blc[b.l])return a.r < b.r;return a.l < b.l;
}int cmpi(yuu a, yuu b)
{return a.id < b.id;
}int main()
{int n, m;scanf("%d%d", &n, &m);//{MMF(cnt);for(int i = 1; i <= n; i++)scanf("%lld", col + i);int ct = sqrt(n);for(int i = 1; i <= n; i++)//分块blc[i] = (i - 1)/ct + 1;for(int i = 1; i <= m; i++){scanf("%lld%lld", &q[i].l, &q[i].r);q[i].id = i;}sort(q + 1, q + 1 + m, cmp);LL ans = 0;LL ll = 1, rr = 0;for(int i = 1; i <= m; i++){//cout << q[i].l << q[i].r << endl;if(ll > q[i].l)for(int j = ll; j > q[i].l; j--)ans += (2*cnt[col[j - 1]] + 1), cnt[col[j - 1]]++;if(ll < q[i].l)for(int j = ll; j < q[i].l; j++)ans -= (2*cnt[col[j]] - 1), cnt[col[j]]--;if(rr < q[i].r)for(int j = rr; j < q[i].r; j++)ans += (2*cnt[col[j + 1]] + 1), cnt[col[j + 1]]++;if(rr > q[i].r)for(int j = rr; j > q[i].r; j--)ans -= (2*cnt[col[j]] - 1), cnt[col[j]]--;ll = q[i].l;rr = q[i].r;if(q[i].l == q[i].r){q[i].a = 0;q[i].b = 1;continue;}q[i].b = (q[i].r - q[i].l) * (q[i].r - q[i].l + 1);q[i].a = ans - (q[i].r - q[i].l + 1);LL g = __gcd(q[i].b, q[i].a);//cout << ans <<endl;q[i].a /= g;q[i].b /= g;}sort(q + 1, q + 1 + m, cmpi);for(int i = 1; i <= m; i++)printf("%lld/%lld\n", q[i].a, q[i].b);//}return 0;
}
