BZOJ 2038:Zちゃんの靴下

タイトルリンク:http://www.lydsy.com:808/JudgeOnline/problem.php?id=2038
テーマの大意
シーケンスを指定します.
毎回1つの区間を尋ねて、この区間の中で2つの数を選んで、2つの数が同じ確率がどれだけ大きいかを求めます.
アルゴリズム:
この問題は莫隊アルゴリズムテンプレートの問題です.
モキューアルゴリズムは区間問合せクラスの問題を解決する汎用アルゴリズムであり,効率はO(n*sqrt(n))に各問合せの複雑さを乗じたものである.
モキューアルゴリズムには2つの実装方法があり,1つはユークリッド最小生成ツリーであり,1つはブロックアルゴリズムである.
私はブロックアルゴリズムを採用しており、符号化の複雑さは比較的低い.
 
まず質問を押す  sqrt(l)を並べ替え、sqrt(n)個のブロックに分け、各ブロックをrで並べ替える
最後に、前の質問から変更するたびに、次の質問の値が得られます.
全時間的複雑度は,O(n*sqrt(n))に質問ごとの複雑度を乗じたものであり,ここでは証明しない.
この問題は成都試合区に行ったときに作ったので、一ヶ月が過ぎて、ずっと貼り忘れていました.
 
コードは次のとおりです.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <climits>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;

typedef long long LL;
#define mp make_pair
#define fi first
#define nd second
typedef pair <int, int> PII;
typedef pair <PII, int> PIII;

const int maxn = 51000, maxm = 51000;
PIII a[maxm];
long long ans1[maxm], ans2[maxm], cot[maxn];
int c[maxn];
int n, m;

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

void update(int pos, int x, int flg)
{
        ans1[pos] -= cot[c[x]] * cot[c[x]];
        cot[c[x]] += flg;
        ans1[pos] += cot[c[x]] * cot[c[x]];
}

bool cmp(const PIII  &a, const PIII &b)
{
    int posa = a.fi.fi/(int)sqrt(n);
    int posb = b.fi.fi/(int)sqrt(n);
    if(posa == posb)
    {
        return a.fi.nd < b.fi.nd;
    }
    return posa < posb;
}

int main()
{
    while(scanf("%d %d", &n, &m) == 2)
    {
        memset(cot, 0, sizeof(cot));
        for(int i = 1; i <= n; i ++)
        {
            scanf("%d", &c[i]);
        }
        for(int i = 0; i < m; i ++)
        {
            int l, r;
            scanf("%d %d", &l, &r);
            a[i] = mp(mp(l, r), i);
            ans2[i] = r - l + 1;
        }
        sort(a, a + m, cmp);
        for(int i = 0, l = 1, r = 0; i < m; i ++)
        {
            if(i)
            {
                ans1[a[i].nd] = ans1[a[i - 1].nd];
            }
            else
            {
                ans1[i] = 0;
            }
            while(l > a[i].fi.fi)
            {
                l --;
                update(a[i].nd, l, 1);
            }
            while(l < a[i].fi.fi)
            {
                update(a[i].nd, l, -1);
                l ++;
            }
            while(r > a[i].fi.nd)
            {
                update(a[i].nd, r, -1);
                r --;
            }
            while(r < a[i].fi.nd)
            {
                r ++;
                update(a[i].nd, r, 1);
            }
        }
        for(int i = 0; i < m; i ++)
        {
            ans1[i] -= ans2[i];
            ans2[i] *= ans2[i] - 1;
            if(ans1[i])
            {
                long long k = gcd(ans1[i], ans2[i]);
                ans1[i] /= k;
                ans2[i] /= k;
            }
            else
            {
                ans2[i] = 1;
            }
            printf("%lld/%lld
",ans1[i], ans2[i]);
        }
    }
    return 0;
}