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;}

bzoj 2038 莫队入门